arXiv Open Access 2021

Embedding Ray Intersection Graphs and Global Curve Simplification

Mees van de Kerkhof Irina Kostitsyna Maarten Löffler

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CG

Penulis (3)

Mees van de Kerkhof

Irina Kostitsyna

Maarten Löffler

Format Sitasi

APA MLA BibTeX

Kerkhof, M.v.d., Kostitsyna, I., Löffler, M. (2021). Embedding Ray Intersection Graphs and Global Curve Simplification. https://arxiv.org/abs/2109.00042

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓