Split the set of points, algorithm

Question

I'm learning for the test and I can't manage with this problem:

We are given a set of n < 1000 points and an integer d. The task is to create two disjoint sets of points A_1 and A_2 (which union is given set of n points) in such way that the distance (euclidean) between each pair of points from A_i (for i = 1 or 2) is less or equal to d. If it is not possible, print -1.

For example, input:

d = 3, and points:

(5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)

we can create:

A_1 = { (2,3), (1,3), (1,1) }

A_2 = { (5,3), (4,2), (5,2), (5,1) }

since each pair of points from A_i (for i = 1 or 2) are close enough.

I really want to know how to solve it, but no idea. Since n is small, algorithm can be even O(n^2 log n), but I don't know how to start. I was thinking that maybe start with counting the distance between each pair of points, then take two points with maximum distance and place them in to different sets (if their distance is greater than d). Then repeat this step for the rest of pairs, but the problem is how to decide where I can legally put next points. Can anyone help with this algorithm?

Answer 1

Let's consider a simple graph with n nodes (corresponding to the n points). Two nodes are connected if the distance between the two corresponding points is greater that d.

If is is possible to create the two disjoints sets, we must have a bi-partite graphe (if some nodes are not connected to the others, they can be put in any set).

Thus, we only need to test the bipartiteness of the graph which is simple :

http://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness

Answer 2

Think of an array with all the points across the top and all the points down the side.

Fill in the array with a zero in any cell if the two points (left and top) that define the cell are more than d apart and one if the two points are less than d apart.

       (5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)
(5,3),          0      1      0      1      1      1
(1,1),   0             0      1      0      1      0
(4,2),   1      0             0      1      1      1
(1,3),   0      1      0             0      1      0
(5,2),   1      0      1      0             0      1
(2,3),   1      1      1      1      0             0
(5,1)    1      0      1      0      1      0

(Note: You have to fill in the each triangle with the same 0s and 1s flipped.)

Ignore the diagonal. Pay attention to the top-right triangular section.

Skip the 0th column.

Start with the 1st column and, if it doesn't have a 1 in the top row, swap it with another column to its right that has a 1 in the top row. Then swap the same rows too to keep the diagonal blank. (If there isn't one, there is no solution.) [Example: Swap column 2 and 3 and row 2 and 3] Note that the choice of this row may become an optimizing factor.

Move to the next column and if it doesn't have a 1 in the top row, swap with a column to the right that does and swap the corresponding rows. If there is not one, try swapping it with a row below it that has a 1 in that column and do the corresponding column. The rows below it should be ignored if below the diagonal.

We are collecting points in the top left corner of the triangle that have 1's in them. These points can all go in one of the collections.

This is where I get lost in doing this in my head but you have to do a similar process starting in the bottom right corner of the triangle and collecting points that will be in the other collection. Swap rows and corresponding columns to collect 1s in the bottom right corner of the triangle.

Once you have swapped enough rows that you can form a rectangle in the top right corner--a true rectangle without the bottom left corner cut off--and that rectangle contains all the 0's, you have a solution. If you can't do that, there is no solution.

There is a comparison of the lowest row with a 1 in the triangle and the rightmost column with a 1 in the triangle and the cell where they meet. That cell has to be in the triangle for a solution to exist.

(I left you a big "to-do" to find how to interleave the swaps of rows and columns to clean the 0's out of the top-left and bottom-right corners of the triangle. Maybe a discussion here can resolve how to make it work. Or find out it won't work.)

Answer 3

Starting with a distance matrix seems to be a good idea. Then in this distance matrix pick every entry that is greater than d. This entry means that the according points have to be in different sets.

Start with two empty sets and iterate all relevant entries ( > d).

If sets are empty, put the two points into them. Otherwise there are three options:

1. If it is clear which set the points belong to, put them into them (that means, inserting the point preserves the max-distance criterion, which can be obtained from the distance matrix).
2. If the points cannot be inserted into one of the sets, the problem is not solvable.
3. If both sets are possible for both points, we have a problem. I would suggest starting a new pair of point sets and putting the points into them. Then if a subsequent point pair is unclear again, check for the second set pair. If it is yet unclear, check for a third set pair and so on. If a point pair is inserted into a previous set, check the following sets, if points are now clear. At the end you have a list of pairs of sets of points, which can be united as you wish.

---

I just had an idea for a second approach, which is similar, but should be a bit faster.

We also start with the distance matrix.

Additional to the two sets, we maintain a stack, queue or whatever of newly added entries.

So if we pick the first relevant entry from the distance matrix, the points are added to both queues. As long as there is an entry in one of the queues, do the following:

Remove the point from the queue and insert it into the set. If the insertion breaks the max-distance criterion, the problem is not solvable. Examine the row or column in the distance matrix for this very point and extract every relevant entry in this row/column. Add the partner point to the queue of the other set (because this has to be in a different set).

If both queues are empty, add the next relevant entry that has not yet been visited to the queues and start over.

This algorithm has the advantage that the points are processed in the order they can impact each other. Therefore, there is no need for more than one pair of sets.