Removing Popular Faces in Curve Arrangements
A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a randomized FPT-time algorithm where the parameter is the number of popular faces.
Authors
- Zuzana Masárová (ORCID: https://orcid.org/0000-0002-6660-1322)
- Maarten Löffler (ORCID: https://orcid.org/0009-0001-9403-8856)
- Alexandra Weinberger (ORCID: https://orcid.org/0000-0001-8553-6661)
- Phoebe de Nooijer
- Soeren Terziadis (ORCID: https://orcid.org/0000-0001-5161-3841)
- Günter Rote (ORCID: https://orcid.org/0000-0002-0351-5945)
- Tamara Mchedlidze (ORCID: https://orcid.org/0000-0002-1545-5580)
Institutions
- FernUniversität in Hagen (DE)
- Institute of Science and Technology Austria (AT)
- Utrecht University (NL)
- Freie Universität Berlin (DE)
- Eindhoven University of Technology (NL)
Publication Details
- Journal
- Journal of Graph Algorithms and Applications
- Published
- 2024-11-03
- DOI
- https://doi.org/10.7155/jgaa.v28i2.2988
- Primary Topic
- Image Processing and 3D Reconstruction
- Type
- article
- Field-Weighted Citation Impact
- 0.00