## General balanced subdivision of two sets of points in the plane.(English)Zbl 1149.52302

Akiyama, Jin (ed.) et al., Discrete geometry, combinatorics and graph theory. 7th China-Japan conference, CJCDGCGT 2005, Tianjin, China, November 18–20, 2005, Xi’an, China, November 22–24, 2005. Revised selected papers. Berlin: Springer (ISBN 978-3-540-70665-6/pbk). Lecture Notes in Computer Science 4381, 79-87 (2007).
Summary: 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 \cup B$$ are co-linear. Suppose $$ag \leq |R| \leq (a + 1)g, bg \leq |B| \leq (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} \geq 0$$, $$g_{2} \geq 0$$, $$g_{3} \geq 0$$ and $$g_{1} + g_{2} + g_{3} \geq 1$$. We show that the plane can be subdivided into $$g$$ disjoint convex polygons $$X_{1}\cup \cdots \cup X_{g_1}\cup Y_{1}\cup \cdots \cup Y_{g_2}\cup Z_{1}\cup \cdots \cup Z_{g_3}$$ 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 $$b + 1$$ blue points.
For the entire collection see [Zbl 1115.68001].

### MSC:

 52B55 Computational aspects related to convexity
Full Text: