Covering Paths for Planar Point Sets |
| |
Authors: | Adrian Dumitrescu Dániel Gerbner Balázs Keszegh Csaba D. Tóth |
| |
Affiliation: | 1. Computer Science, University of Wisconsin, Milwaukee, USA 2. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary 3. Department of Mathematics, California State University Northridge, Los Angeles, CA, USA 4. Department of Mathematics and Statistics, University of Calgary, Calgary, Canada
|
| |
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/logn) 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 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 Ω(nlogn) time in the worst case. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|