2026-07-22T19:33:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18659 2024-03-06T11:02:23Z ddc:004 open_access

Reconfiguration of Polygonal Subdivisions via Recombination A. Akitaya, Hugo Gonczi, Andrei Souvaine, Diane L. Tóth, Csaba D. Weighill, Thomas configuration space gerrymandering polygonal subdivision recombination Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon ℛ, called a district map, is a set of interior disjoint connected polygons called districts whose union equals ℛ. We consider the recombination as the reconfiguration move which takes a subdivision and produces another by merging two adjacent districts, and by splitting them into two connected polygons of the same area as the original districts. The complexity of a map is the number of vertices in the boundaries of its districts. Given two maps with k districts, with complexity O(n), and a perfect matching between districts of the same area in the two maps, we show constructively that (log n)^O(log k) recombination moves are sufficient to reconfigure one into the other. We also show that Ω(log n) recombination moves are sometimes necessary even when k = 3, thus providing a tight bound when k = 3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Andrei Gonczi and Diane L. Souvaine and Csaba D. Tóth and Thomas Weighill 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.6 urn:nbn:de:0030-drops-186598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.6 eng https://creativecommons.org/licenses/by/4.0/legalcode