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 条

[31] LINEAR ALGORITHM FOR FINDING THE CONVEX-HULL OF A SIMPLE POLYGON
MCCALLUM, D
AVIS, D
INFORMATION PROCESSING LETTERS, 1979, 9 (05) : 201 - 206
[32] NUMERICAL STABILITY OF A CONVEX-HULL ALGORITHM FOR SIMPLE POLYGONS
JAROMCZYK, JW
WASILKOWSKI, GW
ALGORITHMICA, 1993, 10 (06) : 457 - 472
[33] Introducing a simple convex hull method to calibrate diffusion coefficients in Lagrangian particle models
Song, Yang
Fujisaki-Manome, Ayumi
Barker, Christopher H.
Macfadyen, Amy
Titze, Dan
Kessler, James
Wang, Jia
OCEAN ENGINEERING, 2025, 316
[34] Convex hull of points lying on lines in o(n log n) time after preprocessing
Ezra, Esther
Mulzer, Wolfgang
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2013, 46 (04): : 417 - 434
[35] CHoCC: Convex Hull of Cospherical Circles and Applications to Lattices
Wu, Yaohong
Gupta, Ashish
Kurzeja, Kelsey
Rossignac, Jarek
COMPUTER-AIDED DESIGN, 2020, 129
[36] Convex-Hull Algorithms: Implementation, Testing, and Experimentation
Gamby, Ask Neve
Katajainen, Jyrki
ALGORITHMS, 2018, 11 (12):
[37] A Faster Convex-Hull Algorithm via Bucketing
Gamby, Ask Neve
Katajainen, Jyrki
ANALYSIS OF EXPERIMENTAL ALGORITHMS, SEA2 2019, 2019, 11544 : 473 - 489
[38] A CONVEX HULL BASED ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM
Nuriyeva, F.
Kutucu, H.
TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2025, 15 (02): : 412 - 420
[39] THE PARALLEL 3D CONVEX HULL PROBLEM REVISITED
Amato, Nancy M.
Preparata, Franco P.
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (02) : 163 - 173
[40] A method for solving the n-dimensional convex hull problem
Jozwik, Adam
PATTERN RECOGNITION LETTERS, 1983, 2 (01) : 23 - 25

← 1 2 3 4 5 →