SMALLEST ENCLOSING DISKS (BALLS AND ELLIPSOIDS)

被引：313

作者：

WELZL, E

机构：

来源：

LECTURE NOTES IN COMPUTER SCIENCE | 1991年 / 555卷

关键词：

D O I：

10.1007/bfb0038202

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A simple randomized algorithm is developed which computes the smallest enclosing disk of a finite set of points in the plane in expected linear time. The algorithm is based on Seidel's recent Linear Programming algorithm, and it can be generalized to computing smallest enclosing balls or ellipsoids of point sets in higher dimensions in a straightforward way. Experimental results of an implementation are presented.

引用

页码：359 / 370

页数：12

共 18 条

[1] ORDERING OF MULTIVARIATE DATA [J].

BARNETT, V .

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES A-STATISTICS IN SOCIETY, 1976, 139 :318-354

[2] About the smallest circumscribed and the largest inscribed ellipse of a convex area [J].

Behrend, Felix .

MATHEMATISCHE ANNALEN, 1938, 115 :379-411

[3]

CLARKSON KL, 1989, UNPUB LAS VEGAS ALGO

[4]

Danzer L., 1957, ARCH MATH, V8, P214

[5]

DORFLINGER J, 1991, UNPUB APPROXIMATION

[6]

DYER ME, 1987, RANDOMIZED ALGORITHM

[7]

JOHN F, 1948, COURANT ANNIVERSARY, P187

[8]

JUHNKE F, 1990, 490 TU MAGD SEKT MAT

[9]

Jung H, 1901, J REINE ANGEW MATH, V123, P241

[10]

LEICHTWEISS K, 1959, ARCH MATH, V10, P187

← 1 2 →