2013/03/01 by Dumitrescu, Adrian, Gerbner, Daniel, Keszegh, Balazs +1 · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1303.0262
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-crossi ng) covering path consisting of n/2 +O(n/logn) straight line segments. If the path is required to be noncrossing, we prove that (1-\eps)n straight line segments suffice for a small constant \eps>0, and we exhibit n-element point sets that require at least 5n/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 Ω(n logn) time in the worst case.