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

共 50 条

[1] A Preprocessing Technique for Fast Convex Hull Computation
Alshamrani, Reham
Alshehri, Fatimah
Kurdi, Heba
11TH INTERNATIONAL CONFERENCE ON AMBIENT SYSTEMS, NETWORKS AND TECHNOLOGIES (ANT) / THE 3RD INTERNATIONAL CONFERENCE ON EMERGING DATA AND INDUSTRY 4.0 (EDI40) / AFFILIATED WORKSHOPS, 2020, 170 : 317 - 324
[2] CONVEX HULL PROBLEM, LATTICE POINTS AND APPLICATIONS
Fanache, Dumitru
JOURNAL OF SCIENCE AND ARTS, 2011, (02) : 163 - 175
[3] α-Concave hull, a generalization of convex hull
Asaeedi, Saeed
Didehvar, Farzad
Mohades, Ali
THEORETICAL COMPUTER SCIENCE, 2017, 702 : 48 - 59
[4] An Efficient Algorithm for Finding the Minimum Perimeter Convex Hull of Disjoint Segments
Li, Nan
Jiang, Bo
Li, Nannan
PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND APPLICATION ENGINEERING (CSAE2018), 2018,
[5] Finding the convex hull of a simple polygon
Sklansky, Jack
PATTERN RECOGNITION LETTERS, 1982, 1 (02) : 79 - 83
[6] An Improved Cellular Automata Based Algorithm for the 45-Convex Hull Problem
Clarridge, Adam G.
Salomaa, Kai
JOURNAL OF CELLULAR AUTOMATA, 2010, 5 (1-2) : 107 - 120
[7] Convex hull results for the warehouse problem
Wolsey, Laurence A.
Yaman, Hande
DISCRETE OPTIMIZATION, 2018, 30 : 108 - 120
[8] Simple and Robust Dynamic Two-Dimensional Convex Hull
Gaede, Emil Toftegaard
Li Gortz, Inge
van der Hoog, Ivor
Krogh, Christoffer
2024 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX, 2024, : 144 - 156
[9] CudaPre2D: A Straightforward Preprocessing Approach for Accelerating 2D Convex Hull Computations on the GPU
Mei, Gang
Guo, Sixu
2018 26TH EUROMICRO INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, AND NETWORK-BASED PROCESSING (PDP 2018), 2018, : 726 - 732
[10] CudaCHPre2D: A straightforward preprocessing approach for accelerating 2D convex hull computations on the GPU
Qin, Jiayu
Mei, Gang
Cuomo, Salvatore
Guo, Sixu
Li, Yixuan
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2020, 32 (10)

← 1 2 3 4 5 →