Optimal Steiner hull algorithm

Given a set Z of n points in the plane, we consider the problem of finding the Steiner hull for Z which is a non-trivial polygon containing every Euclidean Steiner minimal tree for Z. We give an optimal O(n log n) time and O(n) space algorithm exploiting a Delaunay triangulation of Z. If the Delaunay triangulation is given, the algorithm requires linear time and space. Furthermore, we argue that the uniqueness argument for the O(n(3)) time Steiner hull algorithm given in [4] is incorrect, and we give a correct uniqueness proof. (C) 2001 Elsevier Science B.V. All rights reserved.