An optimal convex hull algorithm in any fixed dimension |
| |
Authors: | Bernard Chazelle |
| |
Institution: | (1) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA |
| |
Abstract: | We present a deterministic algorithm for computing the convex hull ofn points inE
d
in optimalO(n logn+n
⌞d/2⌟
) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an
algorithm for computing the Voronoi diagram ofn points ind-space in optimalO(n logn+n
⌜d/2⌝
) time.
This research was supported in part by the National Science Foundation under Grant CCR-9002352 and The Geometry Center, University
of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. A preliminary version of this paper has appeared in
“An optimal convex hull algorithm and new results on cuttings”,Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, October 1991, pp. 29–38. The convex hull algorithm given in the present paper, although similar in spirit, is considerably
simpler than the one given in the proceedings. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|