A simple and efficient preprocessing step for convex hull problem

被引：0

作者：

Heydari, Mohammad ^{[1
]}

Khalifeh, Ashkan ^{[2
]}

Rathour, Laxmi ^{[3
]}

机构：

[1] Univ Isfahan, Dept Comp Sci, Khansar Campus, Esfahan, Iran

[2] Yazd Univ, Dept Stat, Yazd, Iran

[3] Natl Inst Technol, Dept Math, Chaltlang Aizawl 796012, Mizoram, India

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2024年 / 16卷 / 07期

关键词：

Algorithm; convex hull; recursive; ALGORITHM;

D O I：

10.1142/S179383092350091X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper is concerned with a recursive algorithm as a preprocessing step to find the convex hull of n random points uniformly distributed in the plane. For such a set of points, it is shown that eliminating all but O(log n) of points can derive the same convex hull as the input set. Finally it will be shown that the running time of the algorithm is O(n).

引用

页数：9

共 16 条

[1] FAST CONVEX HULL ALGORITHM [J].

AKL, SG ;

TOUSSAINT, GT .

INFORMATION PROCESSING LETTERS, 1978, 7 (05) :219-222

[2] The Quickhull algorithm for convex hulls [J].

Barber, CB ;

Dobkin, DP ;

Huhdanpaa, H .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1996, 22 (04) :469-483

[3] FAST LINEAR EXPECTED-TIME ALGORITHMS FOR COMPUTING MAXIMA AND CONVEX HULLS [J].

BENTLEY, JL ;

CLARKSON, KL ;

LEVINE, DB .

ALGORITHMICA, 1993, 9 (02) :168-183

[4] Isosurface construction in any dimension using convex hulls [J].

Bhaniramka, P ;

Wenger, R ;

Crawfis, R .

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 2004, 10 (02) :130-141

[5]

Bookstein FL., 1992, Morphometric Tools for Landmark Data: Geometry and Biology

[6] Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points [J].

Borgwardt, KH .

DISCRETE & COMPUTATIONAL GEOMETRY, 1997, 17 (01) :79-109

[7]

Golin M., 1988, Proceedings of the Fourth Annual Symposium on Computational Geometry, P153, DOI 10.1145/73393.73409

[8] Affine invariant comparison of point-sets using convex hulls and Hausdorff distances [J].

Gope, C. ;

Kehtarnavaz, N. .

PATTERN RECOGNITION, 2007, 40 (01) :309-320

[9]

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

[10]

Jayaram M A., 2016, American Journal of Intelligent Systems, V6, P48, DOI [10.5923/j.ajis.20160602.03, DOI 10.5923/J.AJIS.20160602.03]

← 1 2 →