Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Transversal of disjoint convex polygons
Author: Chin, F.
Shen, H.
Wang, F.
Citation: Information Processing Letters, 2003; 85(1):55-60
Publisher: Elsevier Science BV
Issue Date: 2003
ISSN: 0020-0190
Statement of
Francis Y. L. Chin, Hong Shen, and Fu Lee Wang
Abstract: Given a set S of n disjoint convex polygons {Pi1in} in a plane, each with ki vertices, the transversal problem is to find, if there exists one, a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N+nlogn) time, where N=∑i=1nki is the total number of vertices of the polygons.
Keywords: Computational geometry; Transversal; Disjoint convex polygon; Stabber
Rights: Copyright © 2002 Elsevier Science B.V. All rights reserved.
RMID: 0020065619
DOI: 10.1016/S0020-0190(02)00414-3
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.