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

被引:38
作者
GREEN, PJ
SILVERMAN, BW
机构
[1] UNIV BATH,BATH BA2 7AY,SOMERSETSHIRE,ENGLAND
[2] UNIV OXFORD,OXFORD,ENGLAND
关键词
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
    BARNETT, V
    [J]. 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
    PREPARATA, FP
    HONG, SJ
    [J]. COMMUNICATIONS OF THE ACM, 1977, 20 (02) : 87 - 93