Randomized quickhull

被引：20
作者：
Wenger, R
机构：
[1] Dept. of Comp. and Info. Science, Ohio State University, Columbus
来源：
ALGORITHMICA | 1997年 / 17卷 / 03期
关键词：
computational geometry; convex hull; randomized algorithm;
D O I：
10.1007/BF02523195
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
This paper contains a simple, randomized algorithm for constructing the convex bull of a set of n points in the plane with expected running time O(n log h) where h is the number of points on the convex hull.
引用
收藏
页码：322 / 329
页数：8
相关论文
共 20 条
[1]   FAST CONVEX HULL ALGORITHM [J].
AKL, SG ;
TOUSSAINT, GT .
INFORMATION PROCESSING LETTERS, 1978, 7 (05) :219-222
[2]  
AVIS D, 1980, INFORM PROCESS LETT, V121, P126
[3]   DIVIDE AND CONQUER FOR LINEAR EXPECTED TIME [J].
BENTLEY, JL ;
SHAMOS, MI .
INFORMATION PROCESSING LETTERS, 1978, 7 (02) :87-91
[4]   CONVEX HULL OF A FINITE SET OF POINTS IN 2 DIMENSIONS [J].
BYKAT, A .
INFORMATION PROCESSING LETTERS, 1978, 7 (06) :296-298
[5]  
Chan T. M., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, P10, DOI 10.1145/220279.220281
[6]  
CHAN TMY, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P282, DOI 10.1109/SBEC.1995.514502
[7]   A RANDOMIZED ALGORITHM FOR CLOSEST-POINT QUERIES [J].
CLARKSON, KL .
SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :830-847
[8]   NEW APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY [J].
CLARKSON, KL .
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :195-222
[9]   APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].
CLARKSON, KL ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421
[10]   HOW TO REDUCE THE AVERAGE COMPLEXITY OF CONVEX-HULL FINDING ALGORITHMS [J].
DEVROYE, L .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1981, 7 (04) :299-308
12