Optimal computation of the Voronoi diagram of disjoint clusters
Let d(a, b) denote the Euclidean distance between two points a. b in the plane. For a cluster C of sites. and for a point p, define d(p. C) = max{d(p, x) / x is an element of C) as the distance between p and C. The Voronoi diagram of a set S of clusters C-1,.... C-m, is a partition of the plane into domains, one for each cluster, such that a point p belongs to the domain of Ci if and only if d(p, C-i) less than or equal to d(p, C-j). i not equal j. In this note. we present an optimal time O(n log n) algorithm for computing the Voronoi diagram of a set of convex-hull disjoint clusters, where n is the sum of cardinalities of all clusters. This improves upon the previous O(n(2)alpha (n)) time bound, where alpha (n) is the inverse Ackermann function. Our result is obtained by examining a new variant of the Voronoi diagram where each site is associated with a convex and unbounded region in which it is active. (C) 2001 Elsevier Science B.V. All rights reserved.
voronoi diagrams of disjoint clusters computational geometry furthest-site voronoi diagrams clusters of points