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 条
  • [21] Edge advancing rules for intersecting spherical convex polygons
    Ha, JS
    Shin, SY
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2002, 12 (03) : 207 - 216
  • [22] An Efficient Algorithm of Convex Hull for Very Large Planar Point Set
    Fan, Guangquan
    Ma, Liping
    Yang, Bingru
    PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON ADVANCES IN COMPUTER SCIENCE AND ENGINEERING (CSE 2013), 2013, 42 : 37 - 40
  • [23] A simple proof of Pach's Extremal Theorem for convex polygons
    Toussaint, Godfried T.
    PATTERN RECOGNITION LETTERS, 1982, 1 (02) : 85 - 86
  • [24] A simple algorithm for Boolean operations on polygons
    Martinez, Francisco
    Ogayar, Carlos
    Jimenez, Juan R.
    Rueda, Antonio J.
    ADVANCES IN ENGINEERING SOFTWARE, 2013, 64 : 11 - 19
  • [25] BISECTIONS AND HAM-SANDWICH CUTS OF CONVEX POLYGONS AND POLYHEDRA
    STOJMENOVIC, I
    INFORMATION PROCESSING LETTERS, 1991, 38 (01) : 15 - 21
  • [26] Faster counting empty convex polygons in a planar point set
    Bae, Sang Won
    INFORMATION PROCESSING LETTERS, 2022, 175
  • [27] A universal trapezoidation algorithm for planar polygons
    Zalik, B
    Clapworthy, GJ
    COMPUTERS & GRAPHICS-UK, 1999, 23 (03): : 353 - 363
  • [28] An Efficient Convex Hull Algorithm Using Affine Transformation in Planar Point Set
    Xing, Changyuan
    Xiong, Zhongyang
    Zhang, Yufang
    Wu, Xuegang
    Dan, Jingpei
    Zhang, Tingping
    ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING, 2014, 39 (11) : 7785 - 7793
  • [29] An Efficient Convex Hull Algorithm Using Affine Transformation in Planar Point Set
    Changyuan Xing
    Zhongyang Xiong
    Yufang Zhang
    Xuegang Wu
    Jingpei Dan
    Tingping Zhang
    Arabian Journal for Science and Engineering, 2014, 39 : 7785 - 7793
  • [30] A novel fingerprint matching and classification schema based on nested convex polygons
    Khazaei, Hamzeh
    Mohades, Ali
    RECENT ADVANCES ON APPLIED MATHEMATICS: PROCEEDINGS OF THE AMERICAN CONFERENCE ON APPLIED MATHEMATICS (MATH '08), 2008, : 419 - +
12345