Covering Paths for Planar Point SetsDumitrescu, Adrian and Tóth, Csaba D. (2013) Covering Paths for Planar Point Sets. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 303314(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractGiven 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 selfcrossing) covering path consisting of $n/2 + O(n/logn)$ straight line segments. If no three points are collinear, any covering path (selfcrossing or noncrossing) needs at least $n/2$ segments. If the path is required to be noncrossing, $n − 1$ straight line segments obviously suffice and we exhibit nelement point sets which require at least $5n/9 − O(1)$ segments in any such path. Further, we show that computing a noncrossing covering path for n points in the plane requires Ω(n logn) time in the worst case.
Actions (login required)
