A CONVEX DEFICIENCY TREE ALGORITHM FOR CURVED POLYGONS

Abstract

Boolean set representations of curved two-dimensional polygons are expressions constructed from planar halfspaces and (possibly regularized) set operations. Such representations arise often in geometric modeling, computer vision, robotics, and computational mechanics. The convex deficiency tree (CDT) algorithm described in this paper constructs such expressions automatically for polygons bounded by linear and curved edges that are subsets of convex curves. The running time of the algorithm is not worse than O(n 2 log n) and the size of the constructed expressions is linear in the number of polygon edges. The algorithm has been fully implemented for polygons bounded by linear and circular edges.