TY - GEN
T1 - A Faster Convex-Hull Algorithm via Bucketing
AU - Gamby, Ask Neve
AU - Katajainen, Jyrki
PY - 2019
Y1 - 2019
N2 - In the convex-hull problem, in two-dimensional space, the task is to find, for a given sequence S of n points, the smallest convex polygon for which each point of S is either in its interior or on its boundary. In this paper, we propose a variant of the classical bucketing algorithm that (1) solves the convex-hull problem for any multiset of points, (2) uses (formula presented) words of extra space, (3) runs in O(n) expected time on points drawn independently and uniformly from a rectangle, and (4) requires (formula presented) time in the worst case. Also, we perform experiments to compare bucketing to other alternatives that are known to work in linear expected time. In our tests, in the integer-coordinate setting, bucketing was a clear winner compared to the considered competitors (plane-sweep, divide & conquer, quickhull, and throw-away).
AB - In the convex-hull problem, in two-dimensional space, the task is to find, for a given sequence S of n points, the smallest convex polygon for which each point of S is either in its interior or on its boundary. In this paper, we propose a variant of the classical bucketing algorithm that (1) solves the convex-hull problem for any multiset of points, (2) uses (formula presented) words of extra space, (3) runs in O(n) expected time on points drawn independently and uniformly from a rectangle, and (4) requires (formula presented) time in the worst case. Also, we perform experiments to compare bucketing to other alternatives that are known to work in linear expected time. In our tests, in the integer-coordinate setting, bucketing was a clear winner compared to the considered competitors (plane-sweep, divide & conquer, quickhull, and throw-away).
KW - Algorithm
KW - Bucketing
KW - Computational geometry
KW - Convex hull
KW - Experimental evaluation
KW - Linear expected time
UR - http://www.scopus.com/inward/record.url?scp=85076391837&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34029-2_30
DO - 10.1007/978-3-030-34029-2_30
M3 - Article in proceedings
AN - SCOPUS:85076391837
SN - 9783030340285
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 473
EP - 489
BT - Analysis of Experimental Algorithms - Special Event,SEA² 2019, Revised Selected Papers
A2 - Kotsireas, Ilias
A2 - Pardalos, Panos
A2 - Tsokas, Arsenis
A2 - Parsopoulos, Konstantinos E.
A2 - Souravlias, Dimitris
PB - Springer VS
T2 - Special Event on Analysis of Experimental Algorithms, SEA² 2019
Y2 - 24 June 2019 through 29 June 2019
ER -