TY - GEN

T1 - A Faster Convex-Hull Algorithm via Bucketing

AU - Neve Gamby, Ask

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 O(n−−√) words of extra space, (3) runs in O(n) expected time on points drawn independently and uniformly from a rectangle, and (4) requires O(nlgn) 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 O(n−−√) words of extra space, (3) runs in O(n) expected time on points drawn independently and uniformly from a rectangle, and (4) requires O(nlgn) 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).

U2 - 10.1007/978-3-030-34029-2_30

DO - 10.1007/978-3-030-34029-2_30

M3 - Article in proceedings

SN - 978-3-030-34028-5

T3 - Lecture Notes in Computer Science

SP - 473

EP - 489

BT - Analysis of Experimental Algorithms. SEA 2019

A2 - Kotsireas, I.

A2 - Pardalos , P.

A2 - Parsopoulos , K.

A2 - Souravlias , D.

A2 - Tsokas, A.

PB - Springer

T2 - SEA: International Symposium on Experimental Algorithms

Y2 - 24 June 2019 through 29 June 2019

ER -