Combinatorial roadmaps in configuration spaces of simple planar polygons

摘要

One-degree-of-freedom mechanisms induced by minimum pseudotriangulations with one convex hull edge removed have been recently introduced by the author to solve a family of non-colliding motion planning problems for planar robot arms (open or closed polygonal chains). They induce canonical roadmaps in configuration spaces of simple planar polygons with fixed edge lengths. While the combinatorial part is well understood, the search for efficient solutions to the algebraic components of the algorithm is posing a number of interesting questions, some of which are addressed in this paper. A list of open problems and further research topics on pointed pseudo-triangulations and related structures motivated by this work is appended.