Streaming algorithms for planar convex hulls

Martín Farach-Colton, Meng Li, Meng-Tsung Tsai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many classical algorithms are known for computing the convex hull of a set of n point in R2 using O(n) space. For large point sets, whose size exceeds the size of the working space, these algorithms cannot be directly used. The current best streaming algorithm for computing the convex hull is computationally expensive, because it needs to solve a set of linear programs. In this paper, we propose simpler and faster streaming and W-stream algorithms for computing the convex hull. Our streaming algorithm has small pass complexity, which is roughly a square root of the current best bound, and it is simpler in the sense that our algorithm mainly relies on computing the convex hulls of smaller point sets. Our W-stream algorithms, one of which is deterministic and the other of which is randomized, have nearly-optimal tradeoff between the pass complexity and space usage, as we established by a new unconditional lower bound.

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsChung-Shou Liao, Wen-Lian Hsu, Der-Tsai Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770941
DOIs
StatePublished - 1 Dec 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

  • Convex Hulls
  • Lower Bounds
  • Streaming Algorithms

Fingerprint Dive into the research topics of 'Streaming algorithms for planar convex hulls'. Together they form a unique fingerprint.

  • Cite this

    Farach-Colton, M., Li, M., & Tsai, M-T. (2018). Streaming algorithms for planar convex hulls. In C-S. Liao, W-L. Hsu, & D-T. Lee (Eds.), 29th International Symposium on Algorithms and Computation, ISAAC 2018 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 123). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2018.47