Orthogonal Equipartitions

Abstract: Consider two absolutely continuous probability measures in the plane. A subdivision of the plane into k>=2 regions is equitable if every region has weight 1/k in each measure. We show that, for any two probability measures in the plane and any integer k>=2, there exists an equitable subdivision of the plane into k regions using at most k-1 horizontal segments and at most k-1 vertical segments. We also prove the existence of orthogonal equipartitions for point measures and present an efficient algorithm for computing an orthogonal equipartition.

An equitable orthogonal partition of 12 blue points and 18 red points. The partition into k=6 regions uses 5 horizontal and 3 vertical segments.

pdf file

@article{b-oe-09
, author = {Sergey Bereg}
, title = {Orthogonal equipartitions}
, journal = {Comput. Geom. Theory Appl.}
, year = {2009}
, volume = {42}
, number = {4}
, pages = {305--314}
, url = {http://dx.doi.org/10.1016/j.comgeo.2008.09.004}
}