Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 382-391
- https://doi.org/10.1109/sfcs.1993.366849
Abstract
We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We show that the combinatorial complexity of a single connected component of the free configuration space of B is k/sup 3/n/sup 2/2/sup O(log(2/3)/ n). This is a significant improvement of the naive bound O((kn)/sup 3/); when k is constant, which is often the case in practice, this yields a near-quadratic bound on the complexity of such a component, which almost settles (in this special case) a long-standing conjecture regarding the complexity of a single cell in a three-dimensional arrangement of surfaces. We also present an algorithm that constructs a single component of the free configuration space of B in time O(n/sup 2+/spl epsi//), for any /spl epsi/>0, assuming B has a constant number of sides. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion planning problem, within the same asymptotic running time.Keywords
This publication has 19 references indexed in Scilit:
- On the Zone Theorem for Hyperplane ArrangementsSIAM Journal on Computing, 1993
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrainsPublished by Association for Computing Machinery (ACM) ,1993
- Castles in the air revisitedPublished by Association for Computing Machinery (ACM) ,1992
- On the complexity of a single cell in certain arrangements of surfaces in 3-space (extended abstract)Published by Association for Computing Machinery (ACM) ,1991
- Triangles in space or building (and analyzing) castles in the airCombinatorica, 1990
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal spaceDiscrete & Computational Geometry, 1990
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysisDiscrete & Computational Geometry, 1989
- Placing the largest similar copy of a convex polygon among polygonal obstaclesPublished by Association for Computing Machinery (ACM) ,1989
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal spaceDiscrete & Computational Geometry, 1987
- Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemesCombinatorica, 1986