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, Redmond, WA, USA , pp. 303-314 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_27).

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
ID Code:1319

Repository Staff Only: item control page

References

Aloupis, G.: A history of linear-time convex hull algorithms for simple polygons, http://cgm.cs.mcgill.ca/~athens/cs601/

Arkin, E.M., Mitchell, J.S.B., Piatko, C.D.: Minimum-link watchman tours. Inf. Proc. Lett. 86, 203–207 (2003)

Bereg, S., Bose, P., Dumitrescu, A., Hurtado, F., Valtr, P.: Traversing a set of points with a minimum number of turns. Discrete Comput. Geom. 41(4), 513–532 (2009)

Brönnimann, H., Chan, T.M.: Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. Comput. Geom. 34, 75–82 (2006)

Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485–524 (1991)

Chvátal, V., Klincsek, G.: Finding largest convex subsets. Congressus Numerantium 29, 453–460 (1980)

Collins, M.J.: Covering a set of points with a minimum number of turns. Internat. J. Comput. Geom. Appl. 14(1-2), 105–114 (2004)

Collins, M.J., Moret, M.E.: Improved lower bounds for the link length of rectilinear spanning paths in grids. Inf. Proc. Lett. 68, 317–319 (1998)

Demaine, E.D., O’Rourke, J.: Open problems from CCCG 2010. In: Proc. 23rd Canadian Conf. Comput. Geom., Toronto, ON, pp. 153–156 (2011)

Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica 2, 463–470 (1935)

Erdős, P., Szekeres, G.: On some extremum problems in elementary geometry. Annales Univ. Sci. Budapest 3-4, 53–62 (1960-1961)

Estivill-Castro, V., Heednacram, A., Suraweera, F.: NP-completeness and FPT results for rectilinear covering problems. Journal of Universal Computer Science 15, 622–652 (2010)

Fulek, R., Keszegh, B., Morić, F., Uljarević, I.: On polygons excluding point sets. In: Proc. 22nd Canadian Conf. Comput. Geom., Winnipeg, MB, pp. 273–276 (2010)

Gerbner, D., Keszegh, B.: Personal Communication (July 2012)

Jiang, M.: On Covering Points with Minimum Turns. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) FAW-AAIM 2012. LNCS, vol. 7285, pp. 58–69. Springer, Heidelberg (2012)

Krizanc, D., Meertens, L.: Link length of rectilinear hamiltonian tours in grids. Ars Combinatoria 38, 177–192 (1994)

Matoušek, J.: Lectures on Discrete Geometry. Springer, New York (2002)

Melkman, A.: On-line construction of the convex hull of a simple polygon. Inf. Proc. Lett. 25(1), 11–12 (1987)

Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, ch. 15, pp. 633–701. Elsevier (2000)

Morić, F.: Separating and covering points in the plane. Communication at the Open Problem Session of the 22nd Canadian Conf. Comput. Geom., Winnipeg, MB (2010)

Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)

Stein, C., Wagner, D.P.: Approximation Algorithms for the Minimum Bends Traveling Salesman Problem. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 406–421. Springer, Heidelberg (2001)

Welzl, E.: Separating and covering points in the plane. In: Communication at the 9th Gremo’s Workshop on Open Problems, Switzerland (February 2011)