Simple and Robust Dynamic Two-Dimensional Convex Hull

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


The convex hull of a data set P is the smallest convex set that contains P. A dynamic data set is one where points are inserted and deleted. In this work, we present a new data structure for convex hull, that allows for efficient dynamic updates, in theory and practice. In a dynamic convex hull implementation, the following traits are desirable: (1) algorithms for efficiently answering queries as to whether a specified point is inside or outside the hull, (2) adhering to geometric robustness, and (3) algorithmic simplicity. Furthermore, a specific but well-motivated type of two-dimensional data is rank-based data. Here, the input is a set of real-valued numbers Y where for any number y ∈ Y its rank is its index in Y 's sorted order. Each value in Y can be mapped to a point (rank, value) to obtain a two-dimensional point set. Note that for a single update, a linear number of (rank, value)-pairs may change; posing a challenge for dynamic algorithms. It is desirable for a dynamic convex hull implementation to also (4) accommodate rank-based data. In this work, we give an efficient, geometrically robust, dynamic convex hull algorithm, that facilitates queries to whether a point is internal. Furthermore, our construction can be used to efficiently update the convex hull of rank-ordered data, when the real-valued point set is subject to insertions and deletions. Our improved solution is based on an algorithmic simplification of the classical convex hull data structure by Overmars and van Leeuwen [STOC'80], combined with new algorithmic insights. Our theoretical guarantees on the update time match those of Overmars and van Leeuwen, namely O(log2 |P|), while we allow a wider range of functionalities (including rank-based data). Our algorithmic simplification includes simplifying an 11-case check down to a 3-case check that can be written in 20 lines of easily readable C-code. We extend our solution to provide a trade-off between theoretical guarantees and the practical performance of our algorithm. We test and compare our solutions extensively on inputs that were generated randomly or adversarially, including benchmarking datasets from the literature.
Original languageEnglish
Title of host publicationProceedings of 2024 SIAM Symposium on Algorithm Engineering and Experiments
PublisherSociety for Industrial and Applied Mathematics
Publication date2024
ISBN (Print)9781611977929
Publication statusPublished - 2024
Event2024 SIAM Symposium on Algorithm Engineering and Experiments - Westin Alexandria Old Town, Alexandria, United States
Duration: 7 Jan 20248 Jan 2024


Conference2024 SIAM Symposium on Algorithm Engineering and Experiments
LocationWestin Alexandria Old Town
Country/TerritoryUnited States


Dive into the research topics of 'Simple and Robust Dynamic Two-Dimensional Convex Hull'. Together they form a unique fingerprint.

Cite this