An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon
| dc.contributor.author | Rappoport, Ari | en_US |
| dc.date.accessioned | 2014-10-21T07:21:17Z | |
| dc.date.available | 2014-10-21T07:21:17Z | |
| dc.date.issued | 1992 | en_US |
| dc.description.abstract | 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 log2 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 log2 n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure. | en_US |
| dc.description.number | 4 | en_US |
| dc.description.seriesinformation | Computer Graphics Forum | en_US |
| dc.description.volume | 11 | en_US |
| dc.identifier.doi | 10.1111/1467-8659.1140235 | en_US |
| dc.identifier.issn | 1467-8659 | en_US |
| dc.identifier.pages | 235-240 | en_US |
| dc.identifier.uri | https://doi.org/10.1111/1467-8659.1140235 | en_US |
| dc.publisher | Blackwell Science Ltd and the Eurographics Association | en_US |
| dc.title | An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon | en_US |