Transversal of disjoint convex polygons. (Q1853175)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Transversal of disjoint convex polygons. |
scientific article; zbMATH DE number 1856505
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Transversal of disjoint convex polygons. |
scientific article; zbMATH DE number 1856505 |
Statements
Transversal of disjoint convex polygons. (English)
0 references
21 January 2003
0 references
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 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+n\log n)\) time, where \(N=\sum_{i=1}^{n}k_{i}\) is the total number of vertices of the polygons.
0 references
Computational geometry
0 references
Transversal
0 references
Disjoint convex polygon
0 references
Stabber
0 references
0.89058566
0 references
0.88782877
0 references
0.8611827
0 references
0.85766435
0 references
0 references
0.8549852
0 references
0 references
0.85320127
0 references
0.85320127
0 references
