On a proposed divide-and-conquer minimal spanning tree algorithm (Q1115202)

\textit{R. Chang} and \textit{R. Lee} [ibid. 26, 7-16 (1986; Zbl 0602.68053)] purport to devise an O(N log N) time minimal spanning tree algorithm for N points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound of \(O(N^ 2 \log N)\). Since it is known that alternate, truly O(N log N) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable.