General Balanced Subdivision of Two Sets of Points in the Plane

摘要

Let R and B be two disjoint sets of red points and blue points, respectively, in the plane such that no three points of R U B are co-linear. Suppose ag ≤ |R| ≤ (a+1)g, bg ≤ |B| ≤ (b+1)g. Then without loss of generality, we can express |R| = a(g_1 + g_2) + (a + 1)g_3, |B| = bg_1 + (b + 1)(g_2 + g_3), where g = g_1 + g_2 + g_3, g_1 ≥ 0, g_2 ≥ 0, g_3 ≥ 0 and g_1 + g_2 +g_3 ≥ 1. We show that the plane can be subdivided into g disjoint convex polygons X_1∪…∪X_(g1) ∪Y_1∪…∪Y_(92)∪Z_1∪…∪ Z_(g3) such that every X_i contains a red points and b blue points, every Y_i contains a red points and b+1 blue points and every Z_i contains a + 1 red points and 6+1 blue points.