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 条
  • [1] A Fast Algorithm for Touring the Disjoint Convex Polygons in the Given Order
    Wang Lijuan
    He Dandan
    Hou Hongfeng
    Jiang Bo
    Ning Tao
    PROCEEDINGS OF 2017 6TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND NETWORK TECHNOLOGY (ICCSNT 2017), 2017, : 107 - 111
  • [2] An Efficient Algorithm for Touring a Sequence of given Convex Polygons in the Plane
    Xu, Changan
    Jiang, Bo
    Wang, Lijuan
    PROCEEDINGS OF 2017 6TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND NETWORK TECHNOLOGY (ICCSNT 2017), 2017, : 74 - 78
  • [3] A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram
    YANG Cheng-lei
    Journal of Zhejiang University Science A(Science in Engineering), 2006, (09) : 1522 - 1529
  • [4] New fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram
    Yang C.-L.
    Qi M.
    Meng X.-X.
    Li X.-Q.
    Wang J.-Y.
    Journal of Zhejiang University-SCIENCE A, 2006, 7 (9): : 1522 - 1529
  • [5] An improved algorithm for intersecting convex polygons
    Saab, YG
    INFORMATION PROCESSING LETTERS, 1997, 61 (02) : 89 - 90
  • [6] A simple linear algorithm for intersecting convex polygons
    Toussaint, Godfried T.
    VISUAL COMPUTER, 1985, 1 (02): : 118 - 123
  • [7] A COUNTEREXAMPLE TO A CONVEX-HULL ALGORITHM FOR POLYGONS
    TOUSSAINT, G
    PATTERN RECOGNITION, 1991, 24 (02) : 183 - 184
  • [8] Visibility of Disjoint Polygons
    Asano, Takao
    Asano, Tetsuo
    Guibas, Leonidas
    Hershberger, John
    Imai, Hiroshi
    ALGORITHMICA, 1986, 1 (1-4) : 49 - 63
  • [9] 2-Approximate Algorithm for Touring a Sequence of Pairwise Disjoint Simple Polygons
    Lyu, Shun
    Jiang, Bo
    2017 2ND INTERNATIONAL CONFERENCE ON COMPUTATIONAL MODELING, SIMULATION AND APPLIED MATHEMATICS (CMSAM), 2017, : 419 - 424
  • [10] Efficient algorithms for counting and reporting pairwise intersections between convex polygons
    Gupta, P
    Janardan, R
    Smid, M
    INFORMATION PROCESSING LETTERS, 1999, 69 (01) : 7 - 13
12345