License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.47
URN: urn:nbn:de:0030-drops-99951
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9995/
Go to the corresponding LIPIcs Volume Portal

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

Streaming Algorithms for Planar Convex Hulls

pdf-format:
LIPIcs-ISAAC-2018-47.pdf (0.5 MB)

Abstract

Many classical algorithms are known for computing the convex hull of a set of n point in R^2 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.

BibTeX - Entry

@InProceedings{farachcolton_et_al:LIPIcs:2018:9995,
  author =	{Mart{\'i}n Farach-Colton and Meng Li and Meng-Tsung Tsai},
  title =	{{Streaming Algorithms for Planar Convex Hulls}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9995},
  URN =		{urn:nbn:de:0030-drops-99951},
  doi =		{10.4230/LIPIcs.ISAAC.2018.47},
  annote =	{Keywords: Convex Hulls, Streaming Algorithms, Lower Bounds}
}

Keywords: Convex Hulls, Streaming Algorithms, Lower Bounds
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI