Veröffentlichung

Titel:

Augmenting Polygons with Matchings

AutorInnen:

Alexander Pilz
Jonathan Rollin
Lena Schlipf
André Schulz

Kategorie:

Workshopbeiträge

erschienen in:

Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)

Abstract:

We study disjoint compatible noncrossing geometric matchings of simple polygons. That is, given a simple polygon P we want to draw a set of pairwise disjoint straight line edges with endpoints on the vertices of P such that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon we show that such a matching with ≤ (n - 4) / 8 edges is not maximal, that is, it can be extended by another compatible matching edge. Complementing this we construct polygons with maximal matchings with n / 6 edges. Finally we consider a related problem. We prove that it is NP-complete to decide whether a noncrossing geometric graph G admits a set of compatible noncrossing edges such that G together with these edges has minimum degree 5.

BibTeX-Eintrag:

@InProceedings{ author = {Alexander Pilz and Jonathan Rollin and Lena Schlipf and Andr{\'e} Schulz}, title = {Augmenting Polygons with Matchings}, booktitle = {36th European Workshop on Computational Geometry (EuroCG'20)}, year = {2020}, }