AN OPTIMAL CONVEX-HULL ALGORITHM IN ANY FIXED DIMENSION

被引：225
作者：
CHAZELLE, B
机构：
[1] Department of Computer Science, Princeton University, Princeton, 08544, NJ
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1993年 / 10卷 / 04期
关键词：
D O I：
10.1007/BF02573985
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a deterministic algorithm for computing the convex hull of n points in E(d) in optimal O(n log n + n right perpendicular d/2 left perpendicular) 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 of n points in d-space in optimal O(n log n + n inverted right perpendicular d/2 inverted left perpendicular) time.
引用
收藏
页码：377 / 409
页数：33
相关论文
共 23 条
[1]   PARTITIONING ARRANGEMENTS OF LINES .1. AN EFFICIENT DETERMINISTIC ALGORITHM [J].
AGARWAL, PK .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) :449-483
[2]  
[Anonymous], 1987, EATCS MONOGRAPHS THE
[3]   VORONOI DIAGRAMS FROM CONVEX HULLS [J].
BROWN, KQ .
INFORMATION PROCESSING LETTERS, 1979, 9 (05) :223-228
[4]   A DETERMINISTIC VIEW OF RANDOM SAMPLING AND ITS USE IN GEOMETRY [J].
CHAZELLE, B ;
FRIEDMAN, J .
COMBINATORICA, 1990, 10 (03) :229-249
[5]   CUTTING HYPERPLANES FOR DIVIDE-AND-CONQUER [J].
CHAZELLE, B .
DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (02) :145-158
[6]  
CHAZELLE B, UNPUB DERANDOMIZING
[7]   A RANDOMIZED ALGORITHM FOR CLOSEST-POINT QUERIES [J].
CLARKSON, KL .
SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :830-847
[8]   APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].
CLARKSON, KL ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421
[9]  
CLARKSON KL, IN PRESS EUCLIDEAN G
[10]   VORONOI DIAGRAMS AND ARRANGEMENTS [J].
EDELSBRUNNER, H ;
SEIDEL, R .
DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (01) :25-44
123