Embedding Ray Intersection Graphs and Global Curve Simplification
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.
keywords: Computational Geometry, Data Imprecision, Trajectories
Conference Proceedings (peer-reviewed)
Irina Kostitsyna, Maarten Löffler, Mees van de Kerkhof
Embedding Ray Intersection Graphs and Global Curve Simplification
Proc. 29th Symposium on Graph Drawing
358–371, 2021
Conference Proceedings (peer-reviewed)
Carola Wenk, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, Mees van de Kerkhof
Global Curve Simplification
Proc. 27th European Symposium on Algorithms
144, 67:1–67:14, 2019
Workshop or Poster (weakly reviewed)
Carola Wenk, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, Mees van de Kerkhof
On Optimal Min-# Curve Simplification Problem
Proc. 28th Fall Workshop on Computational Geometry
, 2018
Archived Publication (not reviewed)
Carola Wenk, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, Mees van de Kerkhof
On Optimal Min-# Curve Simplification Problem
1809.10269, 2018
Archived Publication (not reviewed)
Irina Kostitsyna, Maarten Löffler, Mees van de Kerkhof
Embedding Ray Intersection Graphs and Global Curve Simplification
2109.00042, 2021
back to list