Problem 4 Let R be a set of n red points and G be a set n gr

Problem 4. Let R be a set of n red points and G be a set n green points in the plane such that no three points in RUG are collinear. The task is to connect every red point to a green point by a straight-line segment such that any two segments do not intersect and every green point is connected to a red point. a) Show that there always exists a line passing through one red and one green point the number of red points on one side of the line is equal to the number of green points on the same side. Describe how to find such a line in O(n lg n) time. b) Show that n segments connecting red and green points can be computed in O(n2 lgn) time. Example for b Example for (a).

Solution

(a)

Solution:

Let p be a set of n points in R³ such that not all of them lie in a common plane and no three of them are collinear.

Consider supporting plane to P at P₀ and translate it into the side that contains P.

Let denote the resulting plane.

Project from P₀ all points of P \\ {P₀} on to .

For each pair of elements from plane P1 P` € P \\ {P<sub>0</sub>} , take a line parallel to PP` that passes through P₀ colour with green the intersection point of this line with unless it has been already in red colour.

The set of all green points is denoted by G.

By definition of we have R G = .

We need the following simple property of the sets R and G which implies that a long every line passing through at least two red points either the left most or the right most point belonging to R G is green.

Thus at least two red points belongs to R G

(b)

Solution:

Let P be a set of n = 2m points in general position in the plane. Let {R, G} be a position of P such that |R| = |G| = m.

Consider the points in R are coloured red and the points in B are coloured as green.

A minimum weight RG –matching in k_n (R, G) can be computed in O(n² log n) time.