Weight-Equitable Subdivision of Red and Blue Points in the Plane

• Main Authors: Buot, Jude, Kano, Mikio
• Format: text
• Published: Archīum Ateneo 2018
• Subjects: Weight-equitable subdivision; equitable subdivision; red and blue points in the plane; Mathematics
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/2; https://www.worldscientific.com/doi/abs/10.1142/S0218195918500024
• Institution: Ateneo De Manila University

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.