<p><strong>Theorem 1.</strong> <em>There is an <span class="math-container">$O(n\log n)$</span>-time algorithm for the problem in the post.</em></p>
<p><em>Proof.</em> We first state two utility lemmas, for an arbitrary edge-weighted graph <span class="math-container">$G$</span>.  We postpone their proofs, which are standard, to the end.</p>
<p>Here is the first lemma.  Most likely this is already in the Monma and Suri paper.</p>
<p>Given any bipartition <span class="math-container">$(C_1, C_2)$</span> of <span class="math-container">$G$</span>,
let <span class="math-container">$W(C_1, C_2)$</span> denote the maximum weight of any edge having both endpoints in <span class="math-container">$C_1$</span> or both in <span class="math-container">$C_2$</span>.</p>
<p><strong>Lemma 1.</strong> <em>Let <span class="math-container">$T$</span> be any max-weight spanning tree of <span class="math-container">$G$</span>.
Let <span class="math-container">$(C'_1, C'_2)$</span> be the two-coloring of <span class="math-container">$T$</span> (so that each edge in <span class="math-container">$T$</span> is in <span class="math-container">$C'_1\times C'_2$</span>). Then <span class="math-container">$(C'_1, C'_2)$</span> minimizes <span class="math-container">$W(C'_1, C'_2)$</span>:
for any bipartition <span class="math-container">$(C_1, C_2)$</span> of <span class="math-container">$G$</span>, <span class="math-container">$W(C_1, C_2) \ge W(C'_1, C'_2)$</span>.</em></p>
<p>Here is the second lemma.</p>
<p>Let <span class="math-container">$G=(V, E)$</span> be an arbitrary edge-weighted graph.</p>
<p><strong>Lemma 2.</strong> <em>Let <span class="math-container">$T\subseteq E$</span>  (the edge set of) any max-weight spanning tree of <span class="math-container">$G$</span>.
Let <span class="math-container">$G_F=(V, E\cup F)$</span> be obtained from <span class="math-container">$G$</span> by adding an arbitrary set <span class="math-container">$F$</span> of additional (weighted) edges.
Let <span class="math-container">$T'$</span> be any max-weight spanning tree of the graph <span class="math-container">$G'_F = (V, T\cup F)$</span>.
Then tree <span class="math-container">$T'$</span> is also a max-weight spanning tree of <span class="math-container">$G_F=(V, E\cup F)$</span>.</em></p>
<p>Here is the algorithm,
which takes as input the set <span class="math-container">$F$</span> of <span class="math-container">$n$</span> pairs of points in the Euclidean plane:</p>
<ol>
<li>compute a maximum-weight spanning tree <span class="math-container">$T$</span> of the <span class="math-container">$2n$</span> points</li>
<li>compute a maximum-weight spanning tree <span class="math-container">$T'$</span> of the graph formed by the edges in <span class="math-container">$T\cup F$</span>, with the pairs in <span class="math-container">$F$</span> interpreted as edges with weight <span class="math-container">$+\infty$</span> (see comment below)</li>
<li>let <span class="math-container">$(C^*_1, C^*_2)$</span> be a two-coloring of <span class="math-container">$T'$</span>, and return <span class="math-container">$(C^*_1, C^*_2)$</span></li>
</ol>
<p>(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 <span class="math-container">$+\infty$</span>.)</p>
<p><em>Running time.</em>  Step 1 can be implemented in <span class="math-container">$O(n\log n)$</span> time using the algorithm of Monma and Suri cited in the post.
Step 2 can be implemented in <span class="math-container">$O(n\log n)$</span> time using a standard MST algorithm on the graph defined in Step 2, which has <span class="math-container">$3n-1$</span> edges.
So the running time is <span class="math-container">$O(n\log n)$</span>.</p>
<p><em>Correctness.</em> Let <span class="math-container">$G'$</span> be the complete graph whose nodes are the <span class="math-container">$2n$</span> points, with the weight of each edge <span class="math-container">$(u, v)$</span> equal to the Euclidean distance from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>, unless <span class="math-container">$(u, v)$</span> is one of the given pairs, in which case the weight of <span class="math-container">$(u, v)$</span> is <span class="math-container">$+\infty$</span>.
By Lemma 2 (taking <span class="math-container">$G$</span> to be the complete graph whose vertices are the <span class="math-container">$2n$</span> points with edge weights given by Euclidean distance), <span class="math-container">$T'$</span> (in Step 3) is a maximum-weight spanning tree of <span class="math-container">$G'$</span>.
So, by Lemma 1, the partition <span class="math-container">$(C^*_1, C^*_2)$</span> computed by the algorithm is an optimal solution, in that it minimizes <span class="math-container">$W(C_1, C_2)$</span>.</p>
<p>In the case that <span class="math-container">$W(C^*_1, C^*_2)$</span> is infinite, every bipartition contains an infinite-weight edge, that is, an edge in <span class="math-container">$F$</span>, so the graph with edge set <span class="math-container">$F$</span> is not bipartite, so no bipartition meeting the side constraints exists.</p>
<p>In the remaining case, <span class="math-container">$(C^*_1, C^*_2)$</span> minimizes <span class="math-container">$W$</span>, which, given that <span class="math-container">$W(C^*_1, C^*_2)$</span> is finite, means that <span class="math-container">$(C^*_1, C^*_2)$</span> respects the side constraints.  Because <span class="math-container">$G'$</span> 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 <span class="math-container">$(C^*_1, C^*_2)$</span> also minimizes the maximum of the <em>diameters</em> of <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span>, as desired. <span class="math-container">$~~~\Box$</span></p>
<p>Here are the proofs of the lemmas:</p>
<p><strong>Lemma 1.</strong> <em>Let <span class="math-container">$T$</span> be any max-weight spanning tree of <span class="math-container">$G$</span>.
Let <span class="math-container">$(C'_1, C'_2)$</span> be the two-coloring of <span class="math-container">$T$</span> (so that each edge in <span class="math-container">$T$</span> is in <span class="math-container">$C'_1\times C'_2$</span>). Then <span class="math-container">$(C'_1, C'_2)$</span> minimizes <span class="math-container">$W(C'_1, C'_2)$</span>:
for any bipartition <span class="math-container">$(C_1, C_2)$</span> of <span class="math-container">$G$</span>, <span class="math-container">$W(C_1, C_2) \ge W(C'_1, C'_2)$</span>.</em></p>
<p><em>Proof of Lemma 1.</em></p>
<ol>
<li>Let <span class="math-container">$(u', v')$</span> be an edge with both endpoints in <span class="math-container">$C'_1$</span> or both in <span class="math-container">$C'_2$</span>, and with <span class="math-container">$w(u', v') = W(C'_1, C'_2)$</span>.</li>
<li>Let <span class="math-container">$(C_1, C_2)$</span> be an arbitrary bipartition of the vertices.</li>
<li>If <span class="math-container">$u'$</span> and <span class="math-container">$v'$</span> are both in <span class="math-container">$C_1$</span> or both in <span class="math-container">$C_2$</span>, then <span class="math-container">$W(C_1, C_2) \ge w(u', v') = W(C'_1, C'_2)$</span>.</li>
<li>So assume WLOG that one of <span class="math-container">$u'$</span> or <span class="math-container">$v'$</span> is in <span class="math-container">$C_1$</span> and the other is in <span class="math-container">$C_2$</span>.</li>
<li>Let <span class="math-container">$P$</span> be the path from <span class="math-container">$u'$</span> to <span class="math-container">$v'$</span> in <span class="math-container">$T$</span>.</li>
<li>Because <span class="math-container">$(C'_1, C'_2)$</span> is a two-coloring of <span class="math-container">$T$</span>, and <span class="math-container">$u'$</span> and <span class="math-container">$v'$</span> have the same color, <span class="math-container">$P$</span> has an even number of edges.</li>
<li>Because of this (and because <span class="math-container">$u'$</span> and <span class="math-container">$v'$</span> are not both in <span class="math-container">$C_1$</span> and not both in <span class="math-container">$C_2$</span>), there must be some edge on <span class="math-container">$P$</span> with both endpoints in <span class="math-container">$C_1$</span> or both in <span class="math-container">$C_2$</span>.</li>
<li>Let <span class="math-container">$(u, v)$</span> be such an edge, so <span class="math-container">$W(C_1, C_2) \ge w(u, v)$</span>.</li>
<li>Because <span class="math-container">$T$</span> is a maximum-weight spanning tree, <span class="math-container">$w(u', v')$</span> is at most <span class="math-container">$w(u, v)$</span>.
(Otherwise adding <span class="math-container">$(u', v')$</span> to <span class="math-container">$T$</span> and removing <span class="math-container">$(u, v)$</span> would give a heavier spanning tree.)</li>
<li>So <span class="math-container">$W(C_1, C_2) \ge w(u, v) \ge w(u', v') = W(C'_1, C'_2)$</span>.  <span class="math-container">$~~~~\Box$</span></li>
</ol>
<p><strong>Lemma 2.</strong> <em>Let <span class="math-container">$T\subseteq E$</span>  (the edge set of) any max-weight spanning tree of <span class="math-container">$G$</span>.
Let <span class="math-container">$G_F=(V, E\cup F)$</span> be obtained from <span class="math-container">$G$</span> by adding an arbitrary set <span class="math-container">$F$</span> of additional (weighted) edges.
Let <span class="math-container">$T'$</span> be any max-weight spanning tree of the graph <span class="math-container">$G'_F = (V, T\cup F)$</span>.
Then tree <span class="math-container">$T'$</span> is also a max-weight spanning tree of <span class="math-container">$G_F=(V, E\cup F)$</span>.</em></p>
<p><em>Proof of Lemma 2.</em></p>
<ol>
<li>Clearly <span class="math-container">$T'$</span> is a spanning tree of <span class="math-container">$G_F$</span>.</li>
<li>Among maximum-weight spanning trees of <span class="math-container">$G_F$</span>, let <span class="math-container">$T^*$</span> be one that shares as many edges as possible with <span class="math-container">$T'$</span>.</li>
<li>Assume for contradiction that <span class="math-container">$T^* \ne T'$</span>, so <span class="math-container">$T^*$</span> is heavier than <span class="math-container">$T'$</span>.</li>
<li>Tree <span class="math-container">$T^*$</span> cannot be a spanning tree of <span class="math-container">$G'_F$</span> (because <span class="math-container">$T'$</span> is a max-weight spanning tree of <span class="math-container">$G'_F$</span> but <span class="math-container">$T^*$</span> is heavier).</li>
<li>So <span class="math-container">$T^*$</span> has at least one edge in <span class="math-container">$E\setminus T$</span>.</li>
<li>Let <span class="math-container">$e^*=(u^*, v^*)$</span> be such an edge. Let <span class="math-container">$P$</span> be the path from <span class="math-container">$u^*$</span> to <span class="math-container">$w^*$</span> in <span class="math-container">$T$</span>.</li>
<li>Removing <span class="math-container">$e^*$</span> from <span class="math-container">$T^*$</span> splits it into two subtrees
and some edge <span class="math-container">$e'$</span> from <span class="math-container">$P$</span> connects these two subtrees.</li>
<li>Adding <span class="math-container">$e^*$</span> to <span class="math-container">$T$</span> and removing <span class="math-container">$e'$</span> would give another spanning tree of <span class="math-container">$G$</span>,
which cannot be heavier than <span class="math-container">$T$</span>, so <span class="math-container">$w(e^*) \le w(e')$</span>.</li>
<li>Removing <span class="math-container">$e^*$</span> from <span class="math-container">$T^*$</span> and adding <span class="math-container">$e'$</span> thus gives another spanning tree of <span class="math-container">$G_F$</span>
that is at least as heavy as <span class="math-container">$T^*$</span>, and shares more edges with <span class="math-container">$T$</span>,
contradicting that <span class="math-container">$T^*$</span> shares as many edges as possible with <span class="math-container">$T$</span>. <span class="math-container">$~~~\Box$</span></li>
</ol>

CC BY-SA 4.0
2021-09-21T15:50:21.987Z
2021-09-21T19:27:38.460Z
2021-09-21T19:27:38.460Z
Neal Young
<p>What is a fast algorithm for the following problem?</p>
<blockquote>
<p><strong>input:</strong> <em>a set of <span class="math-container">$n$</span> pairs of points in the Euclidean plane</em></p>
<p><strong>output:</strong> <em>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</em></p>
</blockquote>
<p>The problem without the pair constraints (that is, <em>given a set of points, partition them into two clusters so as to minimize the maximum cluster diameter</em>) can be solved in <span class="math-container">$O(n\log n)$</span> time, e.g. by the following algorithm:</p>
<ol>
<li>compute a maximum-weight spanning tree <span class="math-container">$T$</span> in <span class="math-container">$O(n\log n)$</span> time</li>
<li>two-color <span class="math-container">$T$</span> (so that for every edge of <span class="math-container">$T$</span> the endpoints have different colors)</li>
<li>partition the points according to color</li>
</ol>
<p>This algorithm is due to <a href="https://doi.org/10.1007/BF01840396" rel="nofollow noreferrer">Monma et al</a>.  The algorithm used for Step 1 is due to <a href="https://ci.nii.ac.jp/naid/10006934349/" rel="nofollow noreferrer">Monma and Suri</a>.</p>
<p><em>Note: this post records an answer to a <a href="https://cstheory.stackexchange.com/questions/50494/applying-a-change-in-particular-algorithm">currently deleted post</a>.</em></p>

<cg.comp-geom><clustering><diameter>
partitioning points in the plane into two clusters to minimize maximum cluster diameter
Neal Young
# partitioning points in the plane into two clusters to minimize maximum cluster diameter

(Asked by: username_0 on 2021-09-21)

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](https://doi.org/10.1007/BF01840396). The algorithm used for Step 1 is due to [Monma and Suri](https://ci.nii.ac.jp/naid/10006934349/).

*Note: this post records an answer to a [currently deleted post](https://cstheory.stackexchange.com/questions/50494/applying-a-change-in-particular-algorithm).*

**Tags:** cg.comp-geom, clustering, diameter

---

## 1 answers

### Answer by username_0 on 2021-09-21. Score: 1 | Accepted answer

**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$


---

