partitioning points in the plane into two clusters to minimize maximum cluster diameter

Question

What is a fast algorithm for the following problem?

input: a set of $n$ pairs of points in the Euclidean plane

output: a partition of the points into two clusters so that, for each given pair, the two points are in different clusters, and subject to that constraint the maximum cluster diameter is minimized

The problem without the pair constraints (that is, given a set of points, partition them into two clusters so as to minimize the maximum cluster diameter) can be solved in $O(n\log n)$ time, e.g. by the following algorithm:

1. compute a maximum-weight spanning tree $T$ in $O(n\log n)$ time
2. two-color $T$ (so that for every edge of $T$ the endpoints have different colors)
3. partition the points according to color

This algorithm is due to Monma et al. The algorithm used for Step 1 is due to Monma and Suri.

Note: this post records an answer to a currently deleted post.

Answer 1

Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post.

Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are standard, to the end.

Here is the first lemma. Most likely this is already in the Monma and Suri paper.

Given any bipartition $(C_1, C_2)$ of $G$, let $W(C_1, C_2)$ denote the maximum weight of any edge having both endpoints in $C_1$ or both in $C_2$.

Lemma 1. Let $T$ be any max-weight spanning tree of $G$. Let $(C'_1, C'_2)$ be the two-coloring of $T$ (so that each edge in $T$ is in $C'_1\times C'_2$). Then $(C'_1, C'_2)$ minimizes $W(C'_1, C'_2)$: for any bipartition $(C_1, C_2)$ of $G$, $W(C_1, C_2) \ge W(C'_1, C'_2)$.

Here is the second lemma.

Let $G=(V, E)$ be an arbitrary edge-weighted graph.

Lemma 2. Let $T\subseteq E$ (the edge set of) any max-weight spanning tree of $G$. Let $G_F=(V, E\cup F)$ be obtained from $G$ by adding an arbitrary set $F$ of additional (weighted) edges. Let $T'$ be any max-weight spanning tree of the graph $G'_F = (V, T\cup F)$. Then tree $T'$ is also a max-weight spanning tree of $G_F=(V, E\cup F)$.

Here is the algorithm, which takes as input the set $F$ of $n$ pairs of points in the Euclidean plane:

1. compute a maximum-weight spanning tree $T$ of the $2n$ points
2. compute a maximum-weight spanning tree $T'$ of the graph formed by the edges in $T\cup F$, with the pairs in $F$ interpreted as edges with weight $+\infty$ (see comment below)
3. let $(C^*_1, C^*_2)$ be a two-coloring of $T'$, and return $(C^*_1, C^*_2)$

(Note on Step 2: here we extend the notion of maximum-weight spanning tree in the natural way so that an optimum tree will first include as many infinite-weight edges as possible, and subject to that constraint will maximize the total weight of the finite-weight edges. Equivalently, we could use a suitably large edge weight -- anything larger than the largest previous edge weight -- instead of $+\infty$.)

Running time. Step 1 can be implemented in $O(n\log n)$ time using the algorithm of Monma and Suri cited in the post. Step 2 can be implemented in $O(n\log n)$ time using a standard MST algorithm on the graph defined in Step 2, which has $3n-1$ edges. So the running time is $O(n\log n)$.

Correctness. Let $G'$ be the complete graph whose nodes are the $2n$ points, with the weight of each edge $(u, v)$ equal to the Euclidean distance from $u$ to $v$, unless $(u, v)$ is one of the given pairs, in which case the weight of $(u, v)$ is $+\infty$. By Lemma 2 (taking $G$ to be the complete graph whose vertices are the $2n$ points with edge weights given by Euclidean distance), $T'$ (in Step 3) is a maximum-weight spanning tree of $G'$. So, by Lemma 1, the partition $(C^*_1, C^*_2)$ computed by the algorithm is an optimal solution, in that it minimizes $W(C_1, C_2)$.

In the case that $W(C^*_1, C^*_2)$ is infinite, every bipartition contains an infinite-weight edge, that is, an edge in $F$, so the graph with edge set $F$ is not bipartite, so no bipartition meeting the side constraints exists.

In the remaining case, $(C^*_1, C^*_2)$ minimizes $W$, which, given that $W(C^*_1, C^*_2)$ is finite, means that $(C^*_1, C^*_2)$ respects the side constraints. Because $G'$ is complete and its finite edge weights satisfy the triangle inequality, this means that the diameter of any such cluster equals the maximum weight of any edge within it. So $(C^*_1, C^*_2)$ also minimizes the maximum of the diameters of $C_1$ and $C_2$, as desired. $~~~\Box$

Here are the proofs of the lemmas:

Lemma 1. Let $T$ be any max-weight spanning tree of $G$. Let $(C'_1, C'_2)$ be the two-coloring of $T$ (so that each edge in $T$ is in $C'_1\times C'_2$). Then $(C'_1, C'_2)$ minimizes $W(C'_1, C'_2)$: for any bipartition $(C_1, C_2)$ of $G$, $W(C_1, C_2) \ge W(C'_1, C'_2)$.

Proof of Lemma 1.

1. Let $(u', v')$ be an edge with both endpoints in $C'_1$ or both in $C'_2$, and with $w(u', v') = W(C'_1, C'_2)$.
2. Let $(C_1, C_2)$ be an arbitrary bipartition of the vertices.
3. If $u'$ and $v'$ are both in $C_1$ or both in $C_2$, then $W(C_1, C_2) \ge w(u', v') = W(C'_1, C'_2)$.
4. So assume WLOG that one of $u'$ or $v'$ is in $C_1$ and the other is in $C_2$.
5. Let $P$ be the path from $u'$ to $v'$ in $T$.
6. Because $(C'_1, C'_2)$ is a two-coloring of $T$, and $u'$ and $v'$ have the same color, $P$ has an even number of edges.
7. Because of this (and because $u'$ and $v'$ are not both in $C_1$ and not both in $C_2$), there must be some edge on $P$ with both endpoints in $C_1$ or both in $C_2$.
8. Let $(u, v)$ be such an edge, so $W(C_1, C_2) \ge w(u, v)$.
9. Because $T$ is a maximum-weight spanning tree, $w(u', v')$ is at most $w(u, v)$. (Otherwise adding $(u', v')$ to $T$ and removing $(u, v)$ would give a heavier spanning tree.)
10. So $W(C_1, C_2) \ge w(u, v) \ge w(u', v') = W(C'_1, C'_2)$. $~~~~\Box$

Lemma 2. Let $T\subseteq E$ (the edge set of) any max-weight spanning tree of $G$. Let $G_F=(V, E\cup F)$ be obtained from $G$ by adding an arbitrary set $F$ of additional (weighted) edges. Let $T'$ be any max-weight spanning tree of the graph $G'_F = (V, T\cup F)$. Then tree $T'$ is also a max-weight spanning tree of $G_F=(V, E\cup F)$.

Proof of Lemma 2.

1. Clearly $T'$ is a spanning tree of $G_F$.
2. Among maximum-weight spanning trees of $G_F$, let $T^*$ be one that shares as many edges as possible with $T'$.
3. Assume for contradiction that $T^* \ne T'$, so $T^*$ is heavier than $T'$.
4. Tree $T^*$ cannot be a spanning tree of $G'_F$ (because $T'$ is a max-weight spanning tree of $G'_F$ but $T^*$ is heavier).
5. So $T^*$ has at least one edge in $E\setminus T$.
6. Let $e^*=(u^*, v^*)$ be such an edge. Let $P$ be the path from $u^*$ to $w^*$ in $T$.
7. Removing $e^*$ from $T^*$ splits it into two subtrees and some edge $e'$ from $P$ connects these two subtrees.
8. Adding $e^*$ to $T$ and removing $e'$ would give another spanning tree of $G$, which cannot be heavier than $T$, so $w(e^*) \le w(e')$.
9. Removing $e^*$ from $T^*$ and adding $e'$ thus gives another spanning tree of $G_F$ that is at least as heavy as $T^*$, and shares more edges with $T$, contradicting that $T^*$ shares as many edges as possible with $T$. $~~~\Box$