Generation of Configuration Spaces III: The Case of Moving Algebraic Curves
Changerjit Bajaj, Myungsoo Kim · Purdue e-Pubs (Purdue University System) · 1986
1b.is paper describes the generation of configuration space obstacles in the plane, arising from the motion of objects with algebraic curve boundaries, moving with fixed orientation amongst obstacles bounded by algebraic curves.We show that the boundary of the configuration space obstacles are the envelopes of algebraic ooundary curves of the reversed object, reversed with respect to a reference point of the object, with the reference point moving on the physical obstacle.Two different algebraic methods are given to generate the boundary of the configuration space obstacles, both of time complexity o(nlog2n) for degree n algebraic curves.The task of finding collision free motion is then relatively simple and a number of polynomial time approaches are described.