Streaming algorithms for planar convex hulls

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

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


    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 (US)
    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
    StatePublished - Dec 1 2018
    Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan, Province of China
    Duration: Dec 16 2018Dec 19 2018

    Publication series

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


    Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
    Country/TerritoryTaiwan, Province of China
    CityJiaoxi, Yilan


    • Convex Hulls
    • Lower Bounds
    • Streaming Algorithms

    ASJC Scopus subject areas

    • Software


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

    Cite this