Abstract
We prove that circle graphs (intersection graphs of circle chords) can be embedded as intersection graphs of rays in the plane with polynomial-size bit complexity.
We use this embedding to show that the global curve simplification problem for the directed Hausdorff distance is NP-hard. In this problem, we are given a polygonal curve \(P\) and the goal is to find a second polygonal curve \(P'\) such that the directed Hausdorff distance from \(P'\) to \(P\) is at most a given constant, and the complexity of \(P'\) is as small as possible.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A suitable polyline could also end with \(s_h\), but we will define the polyline to be in this direction for ease of notation.
References
Abam, M.A., de Berg, M., Hachenberger, P., Zarei, A.: Streaming algorithms for line simplification. Discret. Comput. Geom. 43(3), 497–515 (2010)
Agarwal, P.K., Har-Peled, S., Mustafa, N., Wang, Y.: Near linear time approximation algorithm for curve simplification. Algorithmica 42(3–4), 203–219 (2005)
Barequet, G., Chen, D.Z., Daescu, O., Goodrich, M.T., Snoeyink, J.: Efficiently approximating polygonal paths in three and higher dimensions. Algorithmica 33(2), 150–167 (2002)
de Berg, M., van Kreveld, M., Schirra, S.: Topologically correct subdivision simplification using the bandwidth criterion. Cartogr. Geogr. Inf. Syst. 25(4), 243–257 (1998)
Buzer, L.: Optimal simplification of polygonal chain for rendering. In: Proceedings of 23rd Annual ACM Symposium on Computational Geometry (SoCG), pp. 168–174 (2007)
Cabello, S., Jejčič, M.: Refining the hierarchies of classes of geometric intersection graphs. Electron. J. Combin. 24(1), 1–33 (2017)
Cardinal, J., Felsner, S., Miltzow, T., Tompkins, C., Vogtenhuber, B.: Intersection graphs of rays and grounded segments. J. Graph Algorithms Appl. 22(2), 273–295 (2018)
Chalopin, J., Gonçalves, D., Ochem, P.: Planar graphs are in 1-string. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 609–617 (2007)
Chan, S., Chin, F.: Approximation of polygonal curves with minimum number of line segments or minimum error. Int. J. Comput. Geom. Appl. 6(1), 59–77 (1996)
Chen, D.Z., Daescu, O., Hershberger, J., Kogge, P.M., Mi, N., Snoeyink, J.: Polygonal path simplification with angle constraints. Comput. Geom. 32(3), 173–187 (2005)
Damaschke, P.: The Hamiltonian circuit problem for circle graphs is NP-complete. Inf. Process. Lett. 32(1), 1–2 (1989)
Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica 10(2), 112–122 (1973)
Ehrlich, G., Even, S., Tarjan, R.E.: Intersection graphs of curves in the plane. J. Comb. Theory. Ser. B 21, 8–20 (1976)
Godau, M.: A natural metric for curves - computing the distance for polygonal chains and approximation algorithms. In: Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 127–136 (1991)
Golumbic, M.C.: Algorithmic graph theory and perfect graphs (2004)
Hartman, I.A., Newman, I., Ziv, R.: On grid intersection graphs. Discret. Math. 87, 41–52 (1991)
Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function. J. Inf. Process. 9(3), 159–162 (1986)
Imai, H., Iri, M.: Polygonal approximations of a curve - formulations and algorithms. In: Computational Morphology: A Computational Geometric Approach to the Analysis of Form (1988)
Jinjiang, Y., Sanming, Z.: Optimal labelling of unit interval graphs. Appl. Math. 10(3), 337–344 (1995)
van de Kerkhof, M., Kostitsyna, I., Löffler, M., Mirzanezhad, M., Wenk, C.: Global curve simplification. In: Proceedings of the 27th European Symposium on Algorithms (ESA) (2019)
van de Kerkhof, M., Kostitsyna, I., Löffler, M.: Embedding ray intersection graphs and global curve simplification (2021). https://arxiv.org/abs/2109.00042
Kostitsyna, I., Löffler, M., Polishchuk, V., Staals, F.: On the complexity of minimum-link path problems. J. Comput. Geom. 8(2), 80–108 (2017)
Kratochvíl, J., Matoušek, J.: Intersection graphs of segments. J. Comb. Theory, Ser. B 62(2), 289–315 (1994)
van Kreveld, M., Löffler, M., Wiratma, L.: On optimal polyline simplification using the Hausdorff and Fréchet distance. In: Proceedings of the 34th International Symposium on Computational Geometry (SoCG), vol. 56, pp. 1–14 (2018)
McDiarmid, C., Müller, T.: Integer realizations of disk and segment graphs. J. Comb. Theory, Ser. B 103(1), 114–143 (2013)
McKee, T.A., McMorris, F.: Topics in Intersection Graph Theory. Society for Industrial and Applied Mathematics, USA (1999)
Mustata, I.: On subclasses of grid intersection graphs. Doctoral thesis, Technische Universität Berlin, Berlin (2014)
Acknowledgements
The authors would like to thank Birgit Vogtenhuber, Tillman Miltzow, and anonymous reviewers for valuable discussions and suggestions. Mees van de Kerkhof and Maarten Löffler are (partially) supported by the Dutch Research Council under grant 628.011.00. Maarten Löffler is supported by the Dutch Research Council under grant 614.001.50.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
van de Kerkhof, M., Kostitsyna, I., Löffler, M. (2021). Embedding Ray Intersection Graphs and Global Curve Simplification. In: Purchase, H.C., Rutter, I. (eds) Graph Drawing and Network Visualization. GD 2021. Lecture Notes in Computer Science(), vol 12868. Springer, Cham. https://doi.org/10.1007/978-3-030-92931-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-92931-2_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92930-5
Online ISBN: 978-3-030-92931-2
eBook Packages: Computer ScienceComputer Science (R0)