Balanced Subdivisions of Two Sets of Points in the Plane

M. Kano and Miyuki Uno
Department of Computer and Information Sciences,
Ibaraki University, Hitachi, Ibaraki 316-8511, Japan

Abstract

Let R and B be two disjoint sets of red points and blue points in the plane, respectively, such that no three points of RB are collinear, and let a,b and g be positive integers. We show that if ag|R| (a+1)g and bg|B| (b+1)g, then we can subdivide the plane into g convex polygons so that each open convex polygon contains exactly a red points and b blue points, and the remaining points lie on the boundary of the subdivision. This is a generalization of equitable subdivision of ag red points and bg blue points in the plane.