arXiv Open Access 2020

On the complexity of the middle curve problem

Maike Buchin Nicole Funk Amer Krivošija

Lihat Sumber

Abstrak

For a set of curves, Ahn et al. introduced the notion of a middle curve and gave algorithms computing these with run time exponential in the number of curves. Here we study the computational complexity of this problem: we show that it is NP-complete and give approximation algorithms.

Topik & Kata Kunci

cs.CG

Penulis (3)

Maike Buchin

Nicole Funk

Amer Krivošija

Format Sitasi

APA MLA BibTeX

Buchin, M., Funk, N., Krivošija, A. (2020). On the complexity of the middle curve problem. https://arxiv.org/abs/2001.10298

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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