## Abstract

We present a collection of algorithms, all running in time O(n^{ 2} log n α (n)^{ o(α(n)3)}) for some fixed integer s(where α(n) is the inverse Ackermann's function), for constructing a skeleton representation of a suitably generalized "Voronoi diagram" for a ladder moving in a two-dimensional space bounded by polygonal barriers consisting of n line segments. This diagram, which is a two-dimensional subcomplex of the dimensional configuration space of the ladder, is introduced and analyzed in a companion paper by the present authors. The construction of the diagram described in this paper yields a motion-planning algorithm for the ladder which runs within the same time bound given above.

Original language | English (US) |
---|---|

Pages (from-to) | 27-59 |

Number of pages | 33 |

Journal | Algorithmica |

Volume | 2 |

Issue number | 1-4 |

DOIs | |

State | Published - Nov 1987 |

## Keywords

- Configuration space
- Motion planning
- Moving ladder
- Robotics
- Voronoi diagram

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics