Streaming algorithms for planar convex hulls

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

研究成果: Conference 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.

原文English
主出版物標題29th International Symposium on Algorithms and Computation, ISAAC 2018
編輯Chung-Shou Liao, Wen-Lian Hsu, Der-Tsai Lee
發行者Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(電子)9783959770941
DOIs
出版狀態Published - 1 十二月 2018
事件29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan
持續時間: 16 十二月 201819 十二月 2018

出版系列

名字Leibniz International Proceedings in Informatics, LIPIcs
123
ISSN(列印)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
國家Taiwan
城市Jiaoxi, Yilan
期間16/12/1819/12/18

指紋 深入研究「Streaming algorithms for planar convex hulls」主題。共同形成了獨特的指紋。

引用此