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].


52B55 Computational aspects related to convexity
Full Text: DOI