| Title: |
Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces |
| Authors: |
Brunck, Florestan; Chang, Hsien Chih; Löffler, Maarten; Ophelders, Tim; Schlipf, Lena; Sub Geometric Computing; Dujmovic, Vida; Montecchiani, Fabrizio |
| Publication Year: |
2025 |
| Subject Terms: |
Curve Arrangements; Fixed-Parameter Tractability; NP-hardness; Puzzle Generation; Reconfiguration; Software |
| Description: |
We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible). |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/483527 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/483527 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.B115BD87 |
| Database: |
BASE |