@inproceedings{20f6ea483fa54f8f8b52da84761af9e7,
title = "Embedding Ray Intersection Graphs and Global Curve Simplification",
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.",
author = "{van de Kerkhof}, Mees and Irina Kostitsyna and Maarten L{\"o}ffler",
year = "2021",
month = sep,
doi = "10.1007/978-3-030-92931-2_26",
language = "English",
isbn = "978-3-030-92930-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "358–371",
editor = "Purchase, {Helen C. } and Rutter, {Ignaz }",
booktitle = "Graph Drawing and Network Visualization",
edition = "1",
}