𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Transversal of disjoint convex polygons

✍ Scribed by Francis Y.L. Chin; Hong Shen; Fu Lee Wang

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
146 KB
Volume
85
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Given a set S of n disjoint convex polygons {P i | 1 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 = n i=1 k i is the total number of vertices of the polygons.

πŸ“œ SIMILAR VOLUMES

Efficient algorithm for transversal of d
Efficient algorithm for transversal of disjoint convex polygons
✍ Francis Y.L. Chin; Fu Lee Wang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 103 KB

Given a set S of n disjoint convex polygons {P i | 1 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 = n i=1

Asymptotic Enumeration of Convex Polygon
Asymptotic Enumeration of Convex Polygons
✍ Dudley Stark; Nicholas C. Wormald πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 413 KB

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice Z d taking at least one step in every dimension. A polygon on Z d is said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number of d-dimensional convex pol

The morphology of convex polygons
The morphology of convex polygons
✍ Stephan Olariu πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 427 KB