Equitable subdivisions within polygonal regions

DOI10.1016/J.COMGEO.2005.06.003MaRDI QIDQ2489545zbMATH OpenOpenAlexFDO

Authors Sergey Bereg, Prosenjit Bose, David Kirkpatrick

Publication date 28 April 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.06.003

zbMATH Keywords

algorithmconvexHam-Sandwich theorempolygonal regionshortest pathsubdivision

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The authors prove a generalization of the Ham-Sandwich Theorem, [see \textit{J. E. Goodman} and \textit{J. O'Rourke} (eds.), Handbook of discrete and computational geometry (1997; Zbl 0890.52001)]. Specifically, let \(P\) be a simple polygonal region containing \(| R| =kn\) red points and \(| B| =km\) blue points in its interior with \(k\geq 2\). They show that \(P\) can be partitioned into \(k\) relatively-convex regions each of which contains exactly \(n\) red and \(m\) blue points. A region of \(P\) is relatively-convex if it is closed under geodesic (shortest) paths in \(P\). The authors outline an \(O(kN^{2}\log{2}^N)\) time algorithm for computing such a \(k\)-partition, where \(N=| R| +| B| +| P| \).

Recommendations

• Generalizing ham sandwich cuts to equitable subdivisions
• scientific article; zbMATH DE number 1507295
• Finding equitable convex partitions of points in a polygon efficiently
• Weight-equitable subdivision of red and blue points in the plane
• Geodesic ham-sandwich cuts

Cites work

• A characterization of planar graphs by pseudo-line arrangements
• Algorithms for ham-sandwich cuts
• Balanced partitions of two sets of points in the plane
• Constrained equitable 3-cuttings
• Generalizing ham sandwich cuts to equitable subdivisions
• Geodesic ham-sandwich cuts
• scientific article; zbMATH DE number 1182904 (Why is no real title available?)
• scientific article; zbMATH DE number 1507295 (Why is no real title available?)

Cited in

(14)

• Generalizing ham sandwich cuts to equitable subdivisions
• Computational geometric approaches to equitable districting: a survey
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
• Discrete geometry on colored point sets in the plane -- a survey
• Geometric partitioning and robust ad-hoc network design
• Dividing a territory among several vehicles
• Finding equitable convex partitions of points in a polygon efficiently
• scientific article; zbMATH DE number 1507295 (Why is no real title available?)
• Weight-equitable subdivision of red and blue points in the plane
• A survey of mass partitions
• Generalized ham-sandwich cuts
• Diverse partitions of colored points
• Equal-area locus-based convex polygon decomposition

This page was built for publication: Equitable subdivisions within polygonal regions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489545)