AN 0(N LOG2 H) TIME ALGORITHM FOR THE 3-DIMENSIONAL CONVEX-HULL PROBLEM

被引：19

作者：

EDELSBRUNNER, H ^{[1
]}

SHI, WP ^{[1
]}

机构：

[1] UNIV ILLINOIS,COORDINATED SCI LAB,URBANA,IL 61801

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 02期

关键词：

COMPUTATIONAL GEOMETRY; CONVEX HULL; 3-DIMENSIONS; OUTPUT SENSITIVE;

D O I：

10.1137/0220016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time O(n log2 h) and storage O(n), where h is the number of extreme points. This is an improvement of the O(nh) time gift-wrapping algorithm and, if h = 0(2 square root log2n), of the O(n log n) time divide-and-conquer algorithm.

引用

收藏

页码：259 / 269

页数：11

相关论文

共 22 条

[1]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[2] AN ALGORITHM FOR CONVEX POLYTOPES [J].

CHAND, DR ;

KAPUR, SS .

JOURNAL OF THE ACM, 1970, 17 (01) :78-&

[3] APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].

CLARKSON, KL ;

SHOR, PW .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421

[4] SEARCHING AND STORING SIMILAR LISTS [J].

COLE, R .

JOURNAL OF ALGORITHMS, 1986, 7 (02) :202-220

[5] LINEAR TIME ALGORITHMS FOR 2-VARIABLE AND 3-VARIABLE LINEAR-PROGRAMS [J].

DYER, ME .

SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :31-45

[6] OPTIMAL POINT LOCATION IN A MONOTONE SUBDIVISION [J].

EDELSBRUNNER, H ;

GUIBAS, LJ ;

STOLFI, J .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :317-340

[7] SIMULATION OF SIMPLICITY - A TECHNIQUE TO COPE WITH DEGENERATE CASES IN GEOMETRIC ALGORITHMS [J].

EDELSBRUNNER, H ;

MUCKE, EP .

ACM TRANSACTIONS ON GRAPHICS, 1990, 9 (01) :66-104

[8]

Graham R. L., 1972, Information Processing Letters, V1, P132, DOI 10.1016/0020-0190(72)90045-2

[9] EFFICIENT PLANARITY TESTING [J].

HOPCROFT, J ;

TARJAN, R .

JOURNAL OF THE ACM, 1974, 21 (04) :549-568

[10] OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].

KIRKPATRICK, D .

SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35