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

Document Type


Publication Date



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.