Efficient algorithm for transversal of disjoint convex polygons

被引：3
|
作者：
Chin, FYL
Wang, FL [1 ]
机构：
[1] Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Hong Kong, Hong Kong, Peoples R China
[2] Univ Hong Kong, Dept Comp Sci & Informat Syst, Hong Kong, Hong Kong, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2002年 / 83卷 / 03期
关键词：
computational geometry; transversal; disjoint convex polygon; stabber;
D O I：
10.1016/S0020-0190(01)00322-2
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Given a set S of n disjoint convex polygons {P-i \ 1 less than or equal to i less than or equal to n} in a plane, each with k(i) vertices, the transversal problem is to determine whether there exists a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N + n log n) time, where N = Sigma(i)(n) (= 1) k(i) is the total number of vertices of the polygons. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：141 / 144
页数：4
相关论文
共 50 条
  • [41] Adjusted Bare Bones Fireworks Algorithm to Guard Orthogonal Polygons
    Alihodzic, Adis
    Hasanspahic, Damir
    Cunjalo, Fikret
    Smajlovic, Haris
    INTELLIGENT COMPUTING, VOL 2, 2021, 284 : 341 - 356
  • [42] Algorithm for approximation transitional developable surfaces between two polygons
    Obradovic, Ratko
    Popkonstantinovic, Branislav
    Beljin, Branislav
    TECHNICS TECHNOLOGIES EDUCATION MANAGEMENT-TTEM, 2012, 7 (04): : 1907 - 1913
  • [43] An optimal algorithm for one-separation of a set of isothetic polygons
    Datta, A
    Krithivasan, K
    Ottmann, T
    INFORMATION SCIENCES, 2004, 164 (1-4) : 65 - 88
  • [44] A SUBLOGARITHMIC CONVEX-HULL ALGORITHM
    FJALLSTROM, PO
    KATAJAINEN, J
    LEVCOPOULOS, C
    PETERSSON, O
    BIT, 1990, 30 (03): : 378 - 384
  • [45] Two efficient algorithms for determining intersection points between simple polygons
    Zalik, B
    COMPUTERS & GEOSCIENCES, 2000, 26 (02) : 137 - 151
  • [46] A fast algorithm for an envelope construction of a huge set of topologically consistent polygons
    B. zˇalik
    Engineering with Computers, 2003, 19 : 35 - 44
  • [47] A fast algorithm for an envelope construction of a huge set of topologically consistent polygons
    Zalik, B
    ENGINEERING WITH COMPUTERS, 2003, 19 (01) : 35 - 44
  • [48] A linear-time algorithm for covering simple polygons with similar rectangles
    BarYehuda, R
    BenHanoch, E
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1996, 6 (01) : 79 - 102
  • [49] A simple algorithm for computing positively weighted straight skeletons of monotone polygons
    Biedl, Therese
    Held, Martin
    Huber, Stefan
    Kaaser, Dominik
    Palfrader, Peter
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 243 - 247
  • [50] A Laplace transform algorithm for the volume of a convex polytope
    Lasserre, JB
    Zeron, ES
    JOURNAL OF THE ACM, 2001, 48 (06) : 1126 - 1140
12345