A Faster Convex-Hull Algorithm via Bucketing

Ask Neve Gamby, Jyrki Katajainen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

63 Downloads (Pure)


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).
Original languageEnglish
Title of host publicationAnalysis of Experimental Algorithms. SEA 2019
EditorsI. Kotsireas, P. Pardalos , K. Parsopoulos , D. Souravlias , A. Tsokas
Publication date2019
ISBN (Print)978-3-030-34028-5
ISBN (Electronic)978-3-030-34029-2
Publication statusPublished - 2019
EventSEA: International Symposium on Experimental Algorithms - Kalamata, Greece
Duration: 24 Jun 201929 Jun 2019


ConferenceSEA: International Symposium on Experimental Algorithms
SeriesLecture Notes in Computer Science


Dive into the research topics of 'A Faster Convex-Hull Algorithm via Bucketing'. Together they form a unique fingerprint.

Cite this