CONSTRUCTING THE CONVEX HULL OF A SET OF POINTS IN THE PLANE

被引：41

作者：

GREEN, PJ

SILVERMAN, BW

机构：

[1] UNIV BATH,BATH BA2 7AY,SOMERSETSHIRE,ENGLAND

[2] UNIV OXFORD,OXFORD,ENGLAND

来源：

COMPUTER JOURNAL | 1979年 / 22卷 / 03期

关键词：

D O I：

10.1093/comjnl/22.3.262

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A highly efficient algorithm for computing the vertices of the convex hull of a set of points in the plane is described and compared with existing methods. Empirical timings of a FORTRAN implementation of the algorithm show it to be faster than previous methods for most configurations of points. Careful consideration is given throughout to ensure that degenerate configurations, containing collinear or near-collinear points, are handled correctly.

引用

页码：262 / 266

页数：5

共 6 条

[1] ORDERING OF MULTIVARIATE DATA [J].

BARNETT, V .

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

[2]

Bentley J. L., 1977, DIVIDE CONQUER LINEA

[3]

Eddy W. F., 1977, ACM Transactions on Mathematical Software, V3, P411, DOI 10.1145/355759.355768

[4]

Eddy W. F., 1977, ACM Transactions on Mathematical Software, V3, P398, DOI 10.1145/355759.355766

[5]

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

[6] CONVEX HULLS OF FINITE SETS OF POINTS IN 2 AND 3 DIMENSIONS [J].

PREPARATA, FP ;

HONG, SJ .

COMMUNICATIONS OF THE ACM, 1977, 20 (02) :87-93

← 1 →