Weight-Equitable Subdivision of Red and Blue Points in the Plane
Document Type
Article
Publication Date
2018
Abstract
Let R and B be two disjoint sets of red points and blue points, respectively, in the plane in general position. Assign a weight α to each red point B to each blue point, where a and B are positive integers. Define the weight of a region in the plane as the sum of the weights of red and blue points in it. We give necessary and sufficient conditions for the existence of a line that bisects the weight of the plane whenever the total weight aR + BB is 2w, for some integer w ≥ 1. Moreover, we look closely into the special case where a=2 and B=1 since this case is important to generate a weight-equitable subdivision of the plane. Among other results, we show that for any configuration of R ∪ B with total weight 2|R| + |B|= nw, for some integer n ≥ 2 and odd integer w ≥ 1, the plane can be subdivided into n convex regions of weight w if and only if |B| ≥ n. Using the proofs of the main result, we also give a polynomial time algorithm in finding a weight-equitable subdivision in the plane.
Recommended Citation
Weight-Equitable Subdivision of Red and Blue Points in the Plane Jude Buot (Mathematics Department, Ateneo de Manila University, Quezon City, Philippines) and Mikio Kano (Ibaraki University, Hitachi, Ibaraki, Japan) International Journal of Computational Geometry & Applications 2018 28:01, 39-56
