• German
German

Main Navigation

Buchin/Funk/2020a: On the complexity of the middle curve problem

Bibtype Article
Bibkey Buchin/Funk/2020a
Author Buchin, Maike and Funk, Nicole and Krivosija, Amer
Title On the complexity of the middle curve problem
Journal CoRR
Volume abs/2001.10298
Abstract 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.
Note Presented in EuroCG 2020
Year 2020
Projekt SFB876-A2
Url https://arxiv.org/abs/2001.10298
Bibtex Here you can get this literature entry as BibTeX format.