| A faster convex-hull algorithm via bucketing | |
| Authors: | Ask Neve Gamby and Jyrki Katajainen |
| Published in: | Proceedings of the 18th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 11544, Springer (2019), 473–489 |
| Full text: |  PDF (380 kB) |
| DOI: | 10.1007/978-3-030-34029-2_30 |
| Copyright: | © Springer Nature Switzerland AG |
| Abstract: | 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(n lg n) 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). |
| Related: |  HTML (Source code) HTML (Slides) HTML (Errata) |
| BibLATEX: | @inproceedings{GK2019C,
author = {Ask Neve Gamby and Jyrki Katajainen},
title = {A faster convex-hull algorithm via bucketing},
booktitle = {Proceedings of the 18th International Symposium on Experimental
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {11544},
publisher = {Springer},
year = {2019},
pages = {473--489},
}
|