Covering Paths for Planar Point Sets

Dumitrescu, Adrian and Tóth, Csaba D. (2013) Covering Paths for Planar Point Sets. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 303-314(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.

Abstract

Given a set of points, a covering path is a directed polygonal path that visits all the points. We show that for any n points in the plane, there exists a (possibly self-crossing) covering path consisting of $n/2 + O(n/logn)$ straight line segments. If no three points are collinear, any covering path (self-crossing or non-crossing) needs at least $n/2$ segments. If the path is required to be non-crossing, $n − 1$ straight line segments obviously suffice and we exhibit n-element point sets which require at least $5n/9 − O(1)$ segments in any such path. Further, we show that computing a non-crossing covering path for n points in the plane requires Ω(n logn) time in the worst case.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_27
Classifications: P Styles > P.600 Poly-line
Z Theory > Z.250 Geometry
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 Nov 2013 16:34
Last Modified: 03 Feb 2014 13:55
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1319

Actions (login required)

View Item View Item