Document Open Access Logo

Reconfiguration of Polygonal Subdivisions via Recombination

Authors Hugo A. Akitaya , Andrei Gonczi , Diane L. Souvaine , Csaba D. Tóth , Thomas Weighill

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2023.6.pdf
  • Filesize: 1.67 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Social and professional topics → Social engineering attacks
  • Theory of computation → Computational geometry
  • Theory of computation → Nonconvex optimization
Keywords
  • configuration space
  • gerrymandering
  • polygonal subdivision
  • recombination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill. Reconfiguration of Polygonal Subdivisions via Recombination. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.6

Author Details

Hugo A. Akitaya
  • University of Massachusetts Lowell, MA, USA
Andrei Gonczi
  • Tufts University, Medford, MA, USA
Diane L. Souvaine
  • Tufts University, Medford, MA, USA
Csaba D. Tóth
  • California State University Northridge, Los Angeles, CA, USA
  • Tufts University, Medford, MA, USA
Thomas Weighill
  • University of North Carolina Greensboro, NC, USA

Funding

  • Tóth, Csaba D.: Research funded in part by NSF awards DMS-1800734 and DMS-2154347.
  • Weighill, Thomas: Research funded in part by NSF award OIA-1937095.

References

  1. Hugo A Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D Tóth. Recognizing weakly simple polygons. Discrete & Computational Geometry, 58(4):785-821, 2017. Google Scholar
  2. Hugo A. Akitaya, Matthew D. Jones, Matias Korman, Oliver Korten, Christopher Meierfrankenfeld, Michael J. Munje, Diane L. Souvaine, Michael Thramann, and Csaba D. Tóth. Reconfiguration of connected graph partitions. Journal of Graph Theory, 102(1):35-66, 2023. URL: https://doi.org/10.1002/jgt.22856.
  3. Hugo A. Akitaya, Matias Korman, Oliver Korten, Diane L. Souvaine, and Csaba D. Tóth. Reconfiguration of connected graph partitions via recombination. Theoretical Computer Science, 923:13-26, 2022. URL: https://doi.org/10.1016/j.tcs.2022.04.049.
  4. Eric A. Autry, Daniel Carter, Gregory Herschlag, Zach Hunter, and Jonathan C. Mattingly. Multi-scale merge-split Markov chain Monte Carlo for redistricting, 2020. URL: https://arxiv.org/abs/2008.08054.
  5. Thomas Bläsius, Simon D. Fink, and Ignaz Rutter. Synchronized planarity with applications to constrained planarity problems. In Proc. 29th European Symposium on Algorithms (ESA), volume 204 of LIPIcs, pages 19:1-19:14. Schloss Dagstuhl, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.19.
  6. Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule. Spanning tree methods for sampling graph partitions, 2022. URL: https://arxiv.org/abs/2210.01401.
  7. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1655-1670, 2014. URL: https://doi.org/10.1137/1.9781611973730.110.
  8. Jowei Chen and Jonathan Rodden. Unintentional gerrymandering: Political geography and electoral bias in legislatures. Quarterly Journal of Political Science, 8(3):239-269, 2013. URL: https://doi.org/10.1561/100.00012033.
  9. Jowei Chen and Jonathan Rodden. Cutting through the thicket: Redistricting simulations and the detection of partisan gerrymanders. Election Law Journal, 14(4):331-345, 2015. URL: https://doi.org/10.1089/elj.2015.0317.
  10. Maria Chikina, Alan Frieze, and Wesley Pegden. Assessing significance in a Markov chain without mixing. Proceedings of the National Academy of Sciences, 114(11):2860-2864, 2017. URL: https://doi.org/10.1073/pnas.16175401.
  11. Vincent Cohen-Addad, Philip N Klein, and Neal E Young. Balanced centroidal power diagrams for redistricting. In Proc. 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 389-396, 2018. Google Scholar
  12. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, and Maurizio Pizzonia. On embedding a cycle in a plane graph. Discrete Mathematics, 309(7):1856-1869, 2009. URL: https://doi.org/10.1016/j.disc.2007.12.090.
  13. Daryl DeFord and Moon Duchin. Redistricting reform in Virginia: Districting criteria in context. Virginia Policy Review, 12(2):120-146, 2019. Google Scholar
  14. Daryl DeFord, Moon Duchin, and Justin Solomon. Recombination: A family of Markov chains for redistricting. Harvard Data Science Review, March 2021. URL: https://doi.org/10.1162/99608f92.eb30390f.
  15. Benjamin Fifield, Michael Higgins, Kosuke Imai, and Alexander Tarr. Automated redistricting simulation using Markov chain Monte Carlo. Journal of Computational and Graphical Statistics, 29(4):715-728, 2020. URL: https://doi.org/10.1080/10618600.2020.1739532.
  16. Radoslav Fulek and Csaba D. Tóth. Atomic embeddability, clustered planarity, and thickenability. J. ACM, 69(2):13:1-13:34, 2022. URL: https://doi.org/10.1145/3502264.
  17. Gregory Herschlag, Han Sung Kang, Justin Luo, Christy Vaughn Graves, Sachet Bangia, Robert Ravier, and Jonathan C. Mattingly. Quantifying gerrymandering in north carolina. Statistics and Public Policy, 7(1):30-38, 2020. URL: https://doi.org/10.1080/2330443X.2020.1796400.
  18. Gregory Herschlag, Robert Ravier, and Jonathan C. Mattingly. Evaluating partisan gerrymandering in Wisconsin, 2017. URL: https://arxiv.org/abs/1709.01596.
  19. Camille Jordan. Sur les assemblages des lignes. Journal für die reine und angewandte Mathematik, 70:185-190, 1869. Google Scholar
  20. Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. URL: https://doi.org/10.1137/0136016.
  21. Jonathan C. Mattingly and Christy Vaughn. Redistricting and the will of the people, 2014. URL: https://arxiv.org/abs/1410.8796.
  22. Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1-29, 1997. URL: https://doi.org/10.1145/256292.256294.
  23. Elle Najt, Daryl DeFord, and Justin Solomon. Complexity and geometry of sampling connected graph partitions, 2019. URL: https://arxiv.org/abs/1908.08881.
  24. Patti B. Saris, Gary King, Jamal Greene, and Moon Duchin. Redistricting and representation. Bulletin of the American Academy of Arts and Sciences, 71(2):47-58, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact