COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS

被引:24
作者
Guibas, Leonidas [1 ,2 ]
Hershberger, John [1 ]
Snoeyink, Jack [2 ]
机构
[1] Digital Equipment Corp, Syst Res Ctr, Palo Alto, CA 94301 USA
[2] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
关键词
Computational geometry; data structures; convex hull; lower bounds; common tangents;
D O I
10.1142/S0218195991000025
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper, we investigate the problem of finding the common tangents of two convex polygons that intersect in two (unknown) points. First, we give a Theta(log(2) n) bound for algorithms that store the polygons in independent arrays. Second, we show how to beat the lower bound if the vertices of the convex polygons are drawn from a fixed set of n points. We introduce a data structure called a compact interval tree that supports common tangent computations, as well as the standard binary-search-based queries, in O(logn) time apiece. Third, we apply compact interval trees to solve the subpath hull query problem: given a simple path, preprocess it so that we can find the convex hull of a query subpath quickly. With O(nlog n) preprocessing, we can assemble a compact interval tree that represents the convex hull of a query subpath in O(log n) time. In order to represent arrangements of lines implicitly, Edelsbrunner et al. used a less efficient structure, called bridge trees, to solve the subpath hull query problem. Our compact interval trees improve their results by a factor of O(log n). Thus, the present paper replaces the paper on bridge trees referred to by Edelsbrunner et al.
引用
收藏
页码:1 / 22
页数:22
相关论文
共 14 条
  • [1] Agarwal P. K., 1989, Proceedings of the Fifth Annual Symposium on Computational Geometry, P11, DOI 10.1145/73833.73835
  • [2] Chazelle B, 1980, P 12 ANN ACM S THEOR, P146, DOI 10.1145/800141.804662.
  • [3] Fractional Cascading: II. Applications
    Chazelle, Bernard
    Guibas, Leonidas J.
    [J]. ALGORITHMICA, 1986, 1 (1-4) : 163 - 191
  • [4] Driscoll J.R., 1986, P 18 ANN ACM S THEOR, P109
  • [5] IMPLICITLY REPRESENTING ARRANGEMENTS OF LINES OR SEGMENTS
    EDELSBRUNNER, H
    GUIBAS, L
    HERSHBERGER, J
    SEIDEL, R
    SHARIR, M
    SNOEYINK, J
    WELZL, E
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) : 433 - 466
  • [6] Edelsbrunner H, 1987, EATCS MONOGRAPHS THE, V10
  • [7] FINDING THE CONVEX-HULL OF A SIMPLE POLYGON
    GRAHAM, RL
    YAO, FF
    [J]. JOURNAL OF ALGORITHMS, 1983, 4 (04) : 324 - 331
  • [8] GUIBAS LJ, 1989, 37 DEC SYST RES CTR
  • [9] FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS
    HAREL, D
    TARJAN, RE
    [J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (02) : 338 - 355
  • [10] Mehthorn K., 1984, DATA STRUCTURES ALGO