Efficient algorithm for transversal of disjoint convex polygons.

DOI10.1016/S0020-0190(01)00322-2MaRDI QIDQ1853055zbMATH OpenFDO

Authors Francis Y. L. Chin, Fu Lee Wang

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(01)00322-2

zbMATH Keywords

Computational geometryDisjoint convex polygonStabberTransversal

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Transversal of disjoint convex polygons.
• scientific article; zbMATH DE number 3990242
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• Finding transversals for sets of simple geometric figures
• COMPUTING SHORTEST TRANSVERSALS OF SETS

Cites work

• Finding transversals for sets of simple geometric figures
• Linear Programming in Linear Time When the Dimension Is Fixed
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• Stabbing line segments

Cited in

(6)

• Efficient regular polygon dissections
• Transversal of disjoint convex polygons.
• scientific article; zbMATH DE number 3990242 (Why is no real title available?)
• TRANSVERSALS OF FAMILIES OF SETS IN $ \mathbb{R}^n$ AND A CONNECTION BETWEEN THE HELLY AND BORSUK THEOREMS
• Convex partial transversals of planar regions
• Some discrete properties of the space of line transversals to disjoint balls

This page was built for publication: Efficient algorithm for transversal of disjoint convex polygons.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853055)