Line-segment intersection made in-place

被引：10
作者：
Vahrenhold, Jan [1 ]
机构：
[1] Univ Dortmund, Informat 10, D-44221 Dortmund, Germany
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2007年 / 38卷 / 03期
关键词：
space-efficient algorithms; in-place algorithms; line-segment intersection;
D O I：
10.1016/j.comgeo.2006.09.001
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We present a space-efficient algorithm for reporting all k intersections induced by a set of n line segments in the plane. Our algorithm is an in-place variant of Balaban's algorithm and, in the worst case, runs in 0(n log(2) n + k) time using 0(1) extra words of memory in addition to the space used for the input to the algorithm. (C) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：213 / 230
页数：18
相关论文
共 27 条
  • [1] [Anonymous], 2000, Handbook of Computational Geometry
  • [2] Balaban I. J., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, P211, DOI 10.1145/220279.220302
  • [3] BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432
  • [4] Efficient algorithms for line and curve segment intersection using restricted predicates
    Boissonnat, JD
    Snoeyink, J
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2000, 16 (01): : 35 - 52
  • [5] An elementary algorithm for reporting intersections of red/blue curve segments
    Boissonnat, JD
    Vigneron, A
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 21 (03): : 167 - 175
  • [6] BOSE P, 2004, P 20 EUR WORKSH COMP, P65, DOI DOI 10.1016/J.COMGEO.2006.03.006
  • [7] In-place planar convex hull algorithms
    Brönnimann, H
    Iacono, J
    Katajainen, J
    Morin, P
    Morrison, J
    Toussaint, G
    [J]. LATIN 2002: THEORETICAL INFORMATICS, 2002, 2286 : 494 - 507
  • [8] BRONNIMANN H, 2004, P 20 ANN S COMP GEOM, P239
  • [9] AN OPTIMAL ALGORITHM FOR INTERSECTING LINE SEGMENTS IN THE PLANE
    CHAZELLE, B
    EDELSBRUNNER, H
    [J]. JOURNAL OF THE ACM, 1992, 39 (01) : 1 - 54
  • [10] CHAZELLE B, 1984, P 16 ANN ACM S THEOR, P125
123