Generalized Voronoi diagrams for moving a ladder I: topological analysis

Given a bounded open subset O of the plane whose boundary is the union of finitely many polygons, and a real number d>0, a manifold FP (the `free placements') may be defined as the set of placements of a closed oriented line-segment B (a `ladder') of length d inside O. FP is a 3-dimensional manifold. A `Voronoi complex' in the manifold, a 2-dimensional cell complex, is defined by analogy with the classical geometric construction in the plane: within this complex a 1-dimensional subcomplex N, called the skeleton, is defined. It is shown that every component of FP contains a unique component of N, and canonical motions are given to move the ladder to placements within N. In this way, general motion-planning is reduced to searching in a suitable representation of N as a (combinatorial) graph. Efficient construction of N is described in a companion paper.