BOUNDARY EXTRACTION FOR RASTERIZED MOTION PLANNING
Heinrich Müller · Series in machine perception and artificial intelligence · 1995
A method to extract the boundary between the regions in a d-dimensional regular grid is presented. The grid may be a discrete representation of a configuration space in motion planning, and the regions may be the nearest neighborhoods of convex regions into which the obstacle space of the configuration space is partitioned. Then the boundary represents a retraction space of the free space which can be investigated for reachability more efficiently than the whole free space. On the cell complex representation of the boundary which is deduced here, skeletons can be defined which may further reduce the portion of the free space to be searched. From the cell complex, analogous concepts can be derived on the original grid.