Document Open Access Logo

Streaming Algorithms for Planar Convex Hulls

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.47.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Martín Farach-Colton
  • Department of Computer Science, Rutgers University, Piscataway, USA
Meng Li
  • Department of Computer Science, Rutgers University, Piscataway, USA
Meng-Tsung Tsai
  • Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan

Funding

  • Farach-Colton, Martín: This research was supported in part by NSF CCF 1637458, NIH 1 U01 CA198952-01, a NetAPP Faculty Fellowship and a gift from Dell/EMC.
  • Tsai, Meng-Tsung: This research was supported in part by the Ministry of Science and Technology of Taiwan under contract MOST grant 107-2218-E-009- 026-MY3, and the Higher Education Sprout Project of National Chiao Tung University and Ministry of Education (MOE), Taiwan.

Cite AsGet BibTex

Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai. Streaming Algorithms for Planar Convex Hulls. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.47

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Convex Hulls
  • Streaming Algorithms
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. G. Akl. Optimal parallel algorithms for computing convex hulls and for sorting. Computing, 33(1):1-11, 1984. Google Scholar
  2. A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9(5):216-219, 1979. Google Scholar
  3. M. J. Atallah and M. T. Goodrich. Efficient parallel solutions to some geometric problems. Journal of Parallel and Distributed Computing, 3(4):492-507, 1986. Google Scholar
  4. M. J. Atallah and M. T. Goodrich. Parallel Algorithms for Some Functions of Two Convex Polygons. In the 24th Annual Allerton Conference on Comm., Control and Comput., 1986. Google Scholar
  5. B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In PODS, pages 1-16, 2002. Google Scholar
  6. C. B. Barber, D. P. Dobkin, and H. Huhdanpaa. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 22(4):469-483, 1996. Google Scholar
  7. B. K. Bhattacharya and S. Sen. On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm. J. Algorithms, 25(1):177-193, 1997. Google Scholar
  8. P. Bose, A. Maheshwari, P. Morin, J. Morrison, M. Smid, and J. Vahrenhold. Space-efficient Geometric Divide-and-conquer Algorithms. CGTA, 37(3):209-227, 2007. Google Scholar
  9. G. S. Brodal and R. Jacob. Dynamic planar convex hull. In FOCS, pages 617-626, 2002. Google Scholar
  10. H. Brönnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison, and G. T. Toussaint. Space-efficient planar convex hull algorithms. Theor. Comput. Sci., 321(1):25-40, 2004. Google Scholar
  11. T. M. Chan. Output-sensitive construction of convex hulls. PhD thesis, UBC, 1995. Google Scholar
  12. T. M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete and Computational Geometry, 16:361-368, 1996. Google Scholar
  13. T. M. Chan and E. Y. Chen. Multi-Pass Geometric Algorithms. D&CG, 37(1):79-102, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1275-6.
  14. A. Chow. Parallel Algorithms for Geometric Problems. PhD thesis, UIUC, 1980. Google Scholar
  15. C. Demetrescu, B. Escoffier, G. Moruz, and A. Ribichini. Adapting parallel algorithms to the W-Stream model, with applications to graph problems. TCS, 411:3994-4004, 2010. Google Scholar
  16. C. Demetrescu, I. Finocchi, and A. Ribichini. Trading off space for passes in graph streaming Problems. In SODA, pages 714-723, 2006. Google Scholar
  17. H. Edelsbrunner and W. Shi. An O(nlog ² h) Time Algorithm for the Three-Dimensional Convex Hull Problem. SIAM Journal on Computing, 20(2):259–269, 1991. Google Scholar
  18. Martin Farach-Colton, Meng Li, and Meng-Tsung Tsai. Streaming algorithms for planar convex hulls. CoRR, abs/1810.00455, 2018. URL: http://arxiv.org/abs/1810.00455.
  19. M. Ghouse and M. T. Goodrich. In-place techniques for parallel convex-hull algorithm. In SPAA, pages 192-203, 1991. Google Scholar
  20. R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132-133, 1972. Google Scholar
  21. M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. In SIGMOD, pages 58-66, 2001. Google Scholar
  22. S. Guha and A. McGregor. Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination. In ICALP, pages 760-772, 2008. Google Scholar
  23. N. Gupta and S. Sen. Optimal, output-sensitive algorithms for constructing planar hulls in parallel. Computational Geometry, 8(3):151-166, 1997. Google Scholar
  24. J. Hershberger and S. Suri. Adaptive sampling for geometric problems over data streams. Computational Geometry, 39(3):191-208, 2008. Google Scholar
  25. R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18-21, 1973. Google Scholar
  26. M. Kallay. The complexity of incremental convex hull algorithms in R^d. Information Processing Letters, 19(4):197, 1984. Google Scholar
  27. B. Kalyanasundaram and G. Schintger. The Probabilistic Communication Complexity of Set Intersection. SIAM J. Discret. Math., 5(4):545-557, 1992. Google Scholar
  28. D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287-299, 1986. Google Scholar
  29. M. A. Lopez and S. Reisner. Efficient approximation of convex polygons. International Journal of Computational Geometry &Applications, 10(05):445-452, 2000. Google Scholar
  30. M. A. Lopez and S. Reisner. Hausdorff approximation of convex polygons. Computational Geometry, 32(2):139-158, 2005. Google Scholar
  31. J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. In the 19th Symposium on Foundations of Computer Science (FOCS), pages 253-258, 1978. Google Scholar
  32. S. Muthu. Data streams: algorithms and applications. Now Publishers, 2006. Google Scholar
  33. M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2):166-204, 1981. Google Scholar
  34. F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM, 20(2):87-93, 1977. Google Scholar
  35. R. A. Rufai and D. S. Richards. A Streaming Algorithm for the Convex Hull. In the 27th Canadian Conference on Computational Geometry (CCCG), pages 165-172, 2015. Google Scholar
  36. J. M. Ruhl. Efficient Algorithms for New Computational Models. PhD thesis, MIT, 2003. Google Scholar
  37. M. I. Shamos. Computational Geometry. PhD thesis, Yale University, 1978. Google Scholar
  38. G. T. Toussaint. Solving geometric problems with the rotating calipers. In IEEE 2nd Mediterranean Electrotechnical Conference (MELECON), 1983. Google Scholar
  39. C. N. Yu, M. Crouch, R. Chen, and A. Sala. Online algorithm for approximate quantile queries on sliding windows. In SEA, pages 369-384, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact