An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon
No Thumbnail Available
Date
1992
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Blackwell Science Ltd and the Eurographics Association
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.
Description
@article{10.1111:1467-8659.1140235,
journal = {Computer Graphics Forum},
title = {{An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon}},
author = {Rappoport, Ari},
year = {1992},
publisher = {Blackwell Science Ltd and the Eurographics Association},
ISSN = {1467-8659},
DOI = {10.1111/1467-8659.1140235}
}