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 条

[21] Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure
Felipe Castro, Juan
Romero, Miguel
Gutierrez, Gilberto
Caniupan, Monica
Quijada-Fuentes, Carlos
KNOWLEDGE AND INFORMATION SYSTEMS, 2020, 62 (10) : 4091 - 4111
[22] Convex Hull Aided Registration Method (CHARM)
Fan, Jingfan
Yang, Jian
Zhao, Yitian
Ai, Danni
Liu, Yonghuai
Wang, Ge
Wang, Yongtian
IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 2017, 23 (09) : 2042 - 2055
[23] A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON
Hu Zhanqi Li Yupeng Wang Jun Qiao Lei
CADDM, 1997, (01) : 61 - 64
[24] New algorithm to construct a planar convex hull
Buitrago, Oscar Y.
Ramírez, Andrés L.
Britto, Rodrigo A.
Informacion Tecnologica, 2015, 26 (04): : 137 - 144
[25] Inner δ-approximation of the convex hull of finite sets
Hoang, Nam-Dung
Linh, Nguyen Kieu
Phu, Hoang Xuan
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2025,
[26] Convex Hull Calculation Approach Based on BST
Matrokhin, Dmitry
Golovanov, Roman
PROCEEDINGS OF THE 2018 IEEE CONFERENCE OF RUSSIAN YOUNG RESEARCHERS IN ELECTRICAL AND ELECTRONIC ENGINEERING (EICONRUS), 2018, : 1549 - 1552
[27] Finding Convex Hull Vertices in Metric Space
Zhong, Jinhong
Tang, Ke
Qin, A. K.
PROCEEDINGS OF THE 2014 INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS (IJCNN), 2014, : 1587 - 1592
[28] Efficient convex hull computation for planar freeform curves
Kim, Yong-Joon
Lee, Jieun
Kim, Myung-Soo
Elber, Gershon
COMPUTERS & GRAPHICS-UK, 2011, 35 (03): : 698 - 705
[29] A New Highly Efficient Preprocessing Algorithm for Convex Hull, Maximum Distance and Minimal Bounding Circle in E2: Efficiency Analysis
Skala, Vaclav
COMPUTATIONAL SCIENCE, ICCS 2024, PT III, 2024, 14834 : 54 - 61
[30] ON THE CONVEX-HULL OF THE SIMPLE INTEGER RECOURSE OBJECTIVE FUNCTION
HANEVELD, WKK
STOUGIE, L
VANDERVLERK, MH
ANNALS OF OPERATIONS RESEARCH, 1995, 56 : 209 - 224

← 1 2 3 4 5 →