##
An Efficient Adaptive Algorithm for Constructing the Convex
Differences Tree of a Simple Polygon

The convex differences tree (CDT)
representation of a simple polygon is useful in computer graphics,
computer vision, computer aided design and robotics. The root of the
tree contains the convex hull of the polygon and there is a child
node recursively representing every connectivity component of the set
difference between the convex hull and the polygon. We give an O(n
log K + K log ^2 n) time algorithm for constructing the CDT,
where * n * is the number of polygon vertices and
K is the number of nodes in the CDT.

The algorithm is adaptive to a complexity measure
defined on its output while still being worst case efficient. For
simply shaped polygons, where K is a constant, the algorithm is linear.
In the worst case K= O(n) and the complexity is O(n log ^2 n).
We also give an O(n log n) algorithm which is an application of the recently
introduced compact interval tree data structure.

* Computer Graphics Forum, * 11(4):235-240, 1992.