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)

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(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
PublisherSpringer
Publication date2019
Pages473-489
ISBN (Print)978-3-030-34028-5
ISBN (Electronic)978-3-030-34029-2
DOIs
Publication statusPublished - 2019
EventSEA: International Symposium on Experimental Algorithms - Kalamata, Greece
Duration: 24 Jun 201929 Jun 2019

Conference

ConferenceSEA: International Symposium on Experimental Algorithms
Country/TerritoryGreece
CityKalamata
Period24/06/201929/06/2019
SeriesLecture Notes in Computer Science
Volume11544
ISSN0302-9743

Fingerprint

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

Cite this