Efficient algorithm for transversal of disjoint convex polygons.
type: Item
instance of: scholarly article
title: Efficient algorithm for transversal of disjoint convex polygons.
zbMATH Open document ID: 1043.68102
DOI: 10.1016/S0020-0190(01)00322-2
author: Francis Y. L. Chin
author: Fu Lee Wang
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: Given a set \(S\) of \(n\) disjoint convex polygons \({P_{i}\mid1<i<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=\sum_{i=1}^{n}k_{i}\) is the total number of vertices of the polygons.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52B55
zbMATH DE Number: 1856399
zbMATH Keywords: Computational geometry
zbMATH Keywords: Transversal
zbMATH Keywords: Disjoint convex polygon
zbMATH Keywords: Stabber
MaRDI profile type: Publication
cites work: Linear Time Algorithms for Two- and Three-Variable Linear Programs
cites work: Finding transversals for sets of simple geometric figures
cites work: Stabbing line segments
cites work: Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
cites work: Linear Programming in Linear Time When the Dimension Is Fixed
description: scientific article; zbMATH DE number 1856399