Generation of configuration space obstacles: The case of moving algebraic curves (Q1120268)

The use of configuration space (C-space) to plan motion for a single rigid object among physical obstacles reduces the problem to planning motion for a point among ``grown'' C-space obstacles. The technique relies in efficiently generating the boundary of C-space obstacles. This has previously been done for polygonal objects and obstacles. The present paper considers translatory motion of objects among obstacles with object and obstacle boundaries defined by segments of algebraic plane curves. The C-space obstacle boundary is then shown to be related to the convolution of the boundaries of object and obstacle as well as a certain outer envelope (0-envelope) of curves of the moving object. Several important characterizations connecting algebraic algorithms to the convolution, 0-envelope and boundary are obtained and used to present algebraic algorithms to generate the boundary of the C-space obstacles. The results are too technical to be summarized here.