Given a set of points in the plane, the minimum spanning tree (MST) is the short

Question

Given a set of points in the plane, the minimum spanning tree (MST) is the shortest tree that connects all the points (it minimizes the total edge length). Consider the following divide and conquer strategy for this problem: Sort the points by x-coordinate. Recourse on the [n/2] leftmost points. Recourse on the [n/2] rightmost points. Add the shortest edge that connects a point on the left to a point on the right. Prove that this always returns a spanning tree. Prove or disprove that this always returns an MST.

Explanation / Answer

a)

The given strategy will always return a spanning tree, that is for sure because points are sorted in order from left to right and an edge is connected from left to right in the algorithm which is shortest edge at that point of time. So the point is the given strategy will never create a cycle, because in this case when the points are in sorted order in terms of x coordinate that is impossible that the cycle is generated, the cycle will only generated when a connecting edge is added from right point to left point which is not mentioned in the algorithm. So this proves that the algorithm will always return spanning tree.

b)

Now the question is that whether the given spanning tree will be a minimum spanning tree or not. So the answer is big fat no, because the call in the algorithm is recursive right. It is true that the point are in sorted order but there is a chance the two points in the graph will be selected who have more edge weight instead of the one which was to be selected because of it's smallest edge weight. If we would have been creating this MST linearly then it definitely should have been a minimum spanning tree.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.