Alok Aggarwal, Maria Klawe
Discrete Applied Mathematics
We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram of n sites in the plane can be computed in Θ(n) time when these sites form the vertices of a convex polygon in, say, counterclockwise order. This settles an open problem in computational geometry. Our techniques can also be used to obtain linear-time algorithms for computing the furthest-site Voronoi diagram and the medial axis of a convex polygon and for deleting a site from a general planar Voronoi diagram. © 1989 Springer-Verlag New York Inc.
Alok Aggarwal, Maria Klawe
Discrete Applied Mathematics
Alok Aggarwal, Jon Kleinberg, et al.
STOC 1996
Alok Aggarwal, Amotz Bar-Noy, et al.
FOCS 1992
Alok Aggarwal, J.S. Chang, et al.
Visual Computer