Semi-balanced partitions of two sets of points and embeddings of rooted forests
Let m be a positive interger and let R-1, R-2 and B be three disjoint set of points in a plane such that no three points of R-1, boolean OR R-2 boolean OR B lie on the same line and vertical bar B vertical bar = (m-1)vertical bar R(1)vertical bar+m vertical bar R(2)vertical bar. Put g = vertical bar R-1 boolean OR R(2)vertical bar. Then there exists asubdivision X-1 boolean OR X-2 boolean OR ... boolean OR X-g of the plane into g disjoint convex polygons such that (i) vertical bar X-i boolean AND (R-1 boolean OR R-2)vertical bar = 1 for all 1 <= i <= g; and (ii) vertical bar X-i boolean AND B vertical bar = m-1 if vertical bar X-i boolean AND R(i)vertical bar = 1, and vertical bar X-i boolean AND B vertical bar = m if vertical bar X-i n R(2)vertical bar = 1. This partition is called a semi-balanced partition, and our proof gives an O(n(4)) time algorithm for finding the above semi-balanced partition, where n = vertical bar R(i)vertical bar + vertical bar R(2)vertical bar + vertical bar B vertical bar. We next apply the above result to the following theorem: Let T-1,..., T-g be g disjoint rooted trees such that vertical bar T(i)vertical bar epsilon {m, m + 1} and v(i) is the root of T-i for all 1 <= i <= 9. Let P be a set of vertical bar T(1)vertical bar + ... + vertical bar T(g)vertical bar points in the plane in general position that contains g specified points p(1),... p(g). Then the rooted forest T-1 boolean OR ... boolean OR T-g can be straight-line embedded onto P so that each v(i) corresponds to p(i) for every 1 <= i <= g.
semi-balanced partition red and blue points line embedding