ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We show that, under reasonable assumptions, any collision-avoiding motion-planning problem for a moving system with two degrees of freedom can be solved in timeO(λ s (n) log2 n), wheren is the number of collision constraints imposed on the system,s is a fixed parameter depending, e.g., on the maximum algebraic degree of these constraints, andλ s (n) is the (almost linear) maximum length of (n, s) Davenport-Schinzel sequences. This follows from an upper bound ofO(λ s (n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187744
