Frage

Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization.

We can solve this problem with Prim's algorithm in $O(n^2)$ which is too slow. I've found an algorithm called Delanuay Triangulation but is there any other ways to solve this problem in $O(n log n)$ or faster?

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top