Given $n$ points in the plane, a emph{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/log{n})$ 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 emph{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 $Omega(n log{n})$ time in the worst case.
تحميل البحث