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 k1 horizontal segments and at most
k1 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{boe09
, author = {Sergey Bereg}
, title = {Orthogonal equipartitions}
, journal = {Comput. Geom. Theory Appl.}
, year = {2009}
, volume = {42}
, number = {4}
, pages = {305314}
, url = {http://dx.doi.org/10.1016/j.comgeo.2008.09.004}
}
