TY - GEN
T1 - Streaming algorithms for planar convex hulls
AU - Farach-Colton, Martín
AU - Li, Meng
AU - Tsai, Meng Tsung
N1 - Publisher Copyright:
© Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai;
PY - 2018/12/1
Y1 - 2018/12/1
N2 - 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.
AB - 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.
KW - Convex Hulls
KW - Lower Bounds
KW - Streaming Algorithms
UR - http://www.scopus.com/inward/record.url?scp=85063685175&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85063685175&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2018.47
DO - 10.4230/LIPIcs.ISAAC.2018.47
M3 - Conference contribution
AN - SCOPUS:85063685175
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 47:1-47:13
BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018
A2 - Liao, Chung-Shou
A2 - Hsu, Wen-Lian
A2 - Lee, Der-Tsai
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018
Y2 - 16 December 2018 through 19 December 2018
ER -