Given a set $P$ of $k$ points in a plane. The Distance Variant problem: partition set $P$ into two subsets $P_{1}, P_{2}$ so you can maximize,

$d(P_{1}, P_{2})$ = min $p \in P_{1}$ min $ q \in P_{2}$ $d(p,q)$, where $d(p,q)$ is the Euclidean distance between $p$ and $q$. So basically, $d(P_{1}, P_{2})$ is the smallest distance between $P_{1}$ and $P_{2}$.

Let's say $G$ is a complete graph with vertex set $P$, and the edge $pq$ has weight $w(pq) = d(p,q)$.$T$ be the MST of $G$, $e$ be the edge in $T$ with the largest weight. Removing $e$ from $T$ would create two components $P_{1}, P_{2}$. Assume edge weights are distinct.

$1.$ What I want to prove is that $d(P_{1}, P_{2}) = w(e)$. I think there must exist some type of lemma which is used to aid this proof. My intuition/attempt: well in $T$ I know by removing $e$ would create two components which separate both $P_{1}, P_{2}$, and what is truly separating these sets, are $e$. Because of this the only path from $P_{1}$ to $P_{2}$ and vice versa is through $e$. Because $e$ is the only path, then it must be smallest distance from $P_{1}$ to $P_{2}$.

$2.$ Curveball, let's say $P^*_{1},P^*_{2}$ are optimal solutions, I also think it would possible to show that is $d(P^*_{1},P^*_{2}) \leq w(e)$, but I am unsure if it is actually possible.

$3.$ Algorithm application: I can somewhat see how this problem can be solved in ${O}(n^2)$, but still debating on which algorithm truly fits.

  • $\begingroup$ Sounds like a very nice exercise to help you learn material on MSTs! Have you tried working through some examples? Have you tried proving it? You need to prove that $d(P_1,P_2) \ge w(e)$ and $d(P_1,P_2) \le w(e)$. Have you tried proving either of those? What did you get? $\endgroup$ – D.W. Apr 2 '15 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.