Back to Search
Start Over
Covering Paths for Planar Point Sets.
- Source :
-
Discrete & Computational Geometry . Mar2014, Vol. 51 Issue 2, p462-484. 23p. - Publication Year :
- 2014
-
Abstract
- Given n points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n−1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of n points in the plane admits a (possibly self-crossing) covering path consisting of n/2+ O( n/log n) straight line segments. If the path is required to be noncrossing, we prove that (1− ε) n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5 n/9− O(1) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for n points in the plane requires Ω( nlog n) time in the worst case. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01795376
- Volume :
- 51
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Discrete & Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 94355539
- Full Text :
- https://doi.org/10.1007/s00454-013-9563-4