I have a set of 2D points: (x1,y1) … (xn,yn). I like to divide the points into two sets such that the closest pair of points in each set is maximized. Is there an algorithm for that?

Clarification: The closest pair of points (both in the same set) in each set is maximized. So it's not k-means (which minimizes the furthest point from the center of the cluster).

CodePudding user response：

To rephrase: nearby pairs of points should go in opposite sets if possible.

My suggestion would be to compute a minimum spanning tree (O(n log n) via your favorite Delaunay triangulation algorithm) and then two-color it with a depth-first search (O(n)).

This maximizes the distance between the two closest points in a single set. We know that this distance is at least d if, when we extract all pairs closer than d, the resulting graph is bipartite. If you imagine that we compute the MST using the inefficient Kruskal's algorithm, which sorts the edges by distance and considers them in order, then it's hopefully clear that this algorithm in essence tries greedily to accommodate the requirements of each edge in order, giving up only when an odd cycle is about to form.

In particular, the nearest neighbor of each node is in the opposite set.