2021/08/31 by Mees van de Kerkhof, van de Kerkhof, Mees, Irina Kostitsyna +3
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Image Processing and 3D Reconstruction
paper · pdf · doi:10.48550/arxiv.2109.00042
openalex publication_date 2021/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.