Weight-Equitable Subdivision of Red and Blue Points in the Plane
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 i...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Published: |
Archīum Ateneo
2018
|
| Subjects: | |
| Online Access: | https://archium.ateneo.edu/mathematics-faculty-pubs/2 https://www.worldscientific.com/doi/abs/10.1142/S0218195918500024 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Ateneo De Manila University |
| Summary: | 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. |
|---|