AN OPTIMAL CONVEX-HULL ALGORITHM IN ANY FIXED DIMENSION

被引：218

作者：

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
AGARWAL, PK
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) : 449 - 483
[2] [Anonymous], 1987, EATCS MONOGRAPHS THE
[3] VORONOI DIAGRAMS FROM CONVEX HULLS
BROWN, KQ
[J]. INFORMATION PROCESSING LETTERS, 1979, 9 (05) : 223 - 228
[4] A DETERMINISTIC VIEW OF RANDOM SAMPLING AND ITS USE IN GEOMETRY
CHAZELLE, B
FRIEDMAN, J
[J]. COMBINATORICA, 1990, 10 (03) : 229 - 249
[5] CUTTING HYPERPLANES FOR DIVIDE-AND-CONQUER
CHAZELLE, B
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (02) : 145 - 158
[6] CHAZELLE B, UNPUB DERANDOMIZING
[7] A RANDOMIZED ALGORITHM FOR CLOSEST-POINT QUERIES
CLARKSON, KL
[J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (04) : 830 - 847
[8] APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2.
CLARKSON, KL
SHOR, PW
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) : 387 - 421
[9] CLARKSON KL, IN PRESS EUCLIDEAN G
[10] VORONOI DIAGRAMS AND ARRANGEMENTS
EDELSBRUNNER, H
SEIDEL, R
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (01) : 25 - 44

← 1 2 3 →