Efficiently approximating the minimum-volume bounding box of a point set in three dimensions

被引：164

作者：

Barequet, G ^{[1
]}

Har-Peled, S

机构：

[1] Technion Israel Inst Technol, Fac Comp Sci, IL-32000 Haifa, Israel

[2] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

[3] Johns Hopkins Univ, Dept Comp Sci, Ctr Geometr Comp, Baltimore, MD 21218 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2001年 / 38卷 / 01期

关键词：

approximation; bounding box;

D O I：

10.1006/jagm.2000.1127

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present an efficient O(n + 1/epsilon (4.5))-time algorithm for computing a (1 + epsilon)-approximation of the minimum-volume bounding box of n points in R-3. We also present a simpler algorithm whose running time is O(n log n + n/epsilon (3)). We give some experimental results with implementations of various variants of the second algorithm. (C) 2001 Academic Press.

引用

页码：91 / 109

页数：19

共 21 条

[1] Approximating shortest paths on a convex polytope in three dimensions [J].

Agarwal, PK ;

HarPeled, S ;

Sharir, M ;

Varadarajan, KR .

JOURNAL OF THE ACM, 1997, 44 (04) :567-584

[2]

ANDREWS GE, 1963, T AM MATH SOC, V106, P270

[3]

Barequet G, 1996, COMPUT GRAPH FORUM, V15, pC387, DOI 10.1111/1467-8659.1530387

[4]

BECKMANN N, 1990, ACM SIGMOD, P322, DOI DOI 10.1145/93597.98741

[5]

BESPAMYATNIKH S, 1997, P 9 CAN C COMP GEOM, P33

[6] Output-sensitive results on convex hulls, extreme points, and related problems [J].

Chan, TM .

DISCRETE & COMPUTATIONAL GEOMETRY, 1996, 16 (04) :369-387

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

CLARKSON, KL ;

SHOR, PW .

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

[8]

Dudley R. M., 1974, Journal of Approximation Theory, V10, P227, DOI 10.1016/0021-9045(74)90120-8

[9] APPROXIMATING THE DIAMETER OF A SET OF POINTS IN THE EUCLIDEAN-SPACE [J].

EGECIOGLU, O ;

KALANTARI, B .

INFORMATION PROCESSING LETTERS, 1989, 32 (04) :205-211

[10]

FALOUTSOS C, 1995, ACM SIGMOD RECORD, V24, P163

← 1 2 3 →