Document Open Access Logo

ParGeo: A Library for Parallel Computational Geometry

Authors Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, Julian Shun

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.88.pdf
  • Filesize: 1.19 MB
  • 19 pages

Document Identifiers

Author Details

Yiqiu Wang
  • CSAIL, MIT, Cambridge MA, USA
Rahul Yesantharao
  • CSAIL, MIT, Cambridge MA, USA
Shangdi Yu
  • CSAIL, MIT, Cambridge MA, USA
Laxman Dhulipala
  • University of Maryland, College Park, MD, USA
Yan Gu
  • University of California, Riverside, CA, USA
Julian Shun
  • CSAIL, MIT, Cambridge, MA, USA

Funding

This research is supported by DOE Early Career Award #DE-SC0018947, NSF CAREER Award #CCF-1845763, Google Faculty Research Award, Google Research Scholar Award, DARPA SDH Award #HR0011-18-3-0007, and Applications Driving Architectures (ADA) Research Center, a JUMP Center co-sponsored by SRC and DARPA.

Cite As Get BibTex

Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. ParGeo: A Library for Parallel Computational Geometry. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.88

Abstract

This paper presents ParGeo, a multicore library for computational geometry. ParGeo contains modules for fundamental tasks including kd-tree based spatial search, spatial graph generation, and algorithms in computational geometry.
We focus on three new algorithmic contributions provided in the library. First, we present a new parallel convex hull algorithm based on a reservation technique to enable parallel modifications to the hull. We also provide the first parallel implementations of the randomized incremental convex hull algorithm as well as a divide-and-conquer convex hull algorithm in ℝ³. Second, for the smallest enclosing ball problem, we propose a new sampling-based algorithm to quickly reduce the size of the data set. We also provide the first parallel implementation of Welzl’s classic algorithm for smallest enclosing ball. Third, we present the BDL-tree, a parallel batch-dynamic kd-tree that allows for efficient parallel updates and k-NN queries over dynamically changing point sets. BDL-trees consist of a log-structured set of kd-trees which can be used to efficiently insert, delete, and query batches of points in parallel.
On 36 cores with two-way hyper-threading, our fastest convex hull algorithm achieves up to 44.7x self-relative parallel speedup and up to 559x speedup against the best existing sequential implementation. Our smallest enclosing ball algorithm using our sampling-based algorithm achieves up to 27.1x self-relative parallel speedup and up to 178x speedup against the best existing sequential implementation. Our implementation of the BDL-tree achieves self-relative parallel speedup of up to 46.1x. Across all of the algorithms in ParGeo, we achieve self-relative parallel speedup of 8.1-46.61x.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Shared memory algorithms
Keywords
  • Computational Geometry
  • Parallel Algorithms
  • Libraries

Metrics

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

Related Versions

Supplementary Materials

References

  1. C++ implementation of the 3d quickhull algorithm. URL: https://github.com/akuukka/quickhull.
  2. The computational geometry algorithms library. URL: https://www.cgal.org/.
  3. Header only 3d quickhull in c99. URL: https://github.com/karimnaaji/3d-quickhull.
  4. A header-only C implementation of the quickhull algorithm for building n-dimensional convex hulls and Delaunay meshes. URL: https://github.com/leomccormack/convhull_3d.
  5. Matlab geometry toolbox for 2d/3d geometric computing. URL: https://github.com/mattools/matGeom.
  6. Qhull. URL: http://www.qhull.org/.
  7. Quickhull3d: A robust 3d convex hull algorithm in Java. URL: https://www.cs.ubc.ca/~lloyd/java/quickhull3d.html.
  8. The Stanford 3d scanning repository. URL: http://graphics.stanford.edu/data/3Dscanrep/.
  9. Pankaj K. Agarwal, Lars Arge, Andrew Danner, and Bryan Holland-Minkley. Cache-oblivious data structures for orthogonal range searching. In Proceedings of the Symposium on Computational Geometry, pages 237-245, 2003. Google Scholar
  10. A. Aggarwal, B. Chazelle, L. Guibas, C. Ó'Dúnlaing, and C. Yap. Parallel computational geometry. Algorithmica, 3(1):293-327, March 1988. Google Scholar
  11. Nancy M. Amato and Franco P. Preparata. The parallel 3d convex hull problem revisited. International Journal of Computational Geometry & Applications, 2(02):163-173, 1992. Google Scholar
  12. Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun. The problem-based benchmark suite (PBBS), v2. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 445-447, 2022. Google Scholar
  13. Lars Arge, Gerth Stølting Brodal, and Rolf Fagerberg. Cache-oblivious data structures. In Handbook of Data Structures and Applications, pages 545-565. Chapman and Hall/CRC, 2018. Google Scholar
  14. C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw., 22(4):469-483, December 1996. Google Scholar
  15. Vicente H.F. Batista, David L. Millman, Sylvain Pion, and Johannes Singler. Parallel geometric algorithms for multi-core computers. Computational Geometry, 43(8):663-677, 2010. Google Scholar
  16. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, September 1975. Google Scholar
  17. Jon Louis Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244-251, 1979. Google Scholar
  18. Jon Louis Bentley and James B Saxe. Decomposable searching problems I. static-to-dynamic transformation. Journal of Algorithms, 1(4):301-358, 1980. Google Scholar
  19. Guy E Blelloch. Vector models for data-parallel computing, volume 2. MIT Press Cambridge, 1990. Google Scholar
  20. Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. ParlayLib - a toolkit for parallel algorithms on shared-memory multicore machines. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures, pages 507-509, 2020. Google Scholar
  21. Guy E. Blelloch and Magdalen Dobson. Parallel nearest neighbors in low dimensions with batch updates. In Proceedings of the Symposium on Algorithm Engineering and Experiments, pages 195-208, 2022. Google Scholar
  22. Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Julian Shun. Internally deterministic parallel algorithms can be fast. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 181-192, 2012. Google Scholar
  23. Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. Parallelism in randomized incremental algorithms. Journal of the ACM, 2020. Google Scholar
  24. Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. Randomized incremental convex hull is highly parallel. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures, pages 103-115, 2020. Google Scholar
  25. Paul B. Callahan and S. Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In ACM-SIAM Symposium on Discrete Algorithms, pages 291-300, 1993. Google Scholar
  26. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67-90, 1995. Google Scholar
  27. Kenneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom, 4:387-421, 1989. Google Scholar
  28. N. Dadoun and D.G. Kirkpatrick. Parallel construction of subdivision hierarchies. Journal of Computer and System Sciences, 39(2):153-165, 1989. Google Scholar
  29. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, second edition, 2000. Google Scholar
  30. Erik D Demaine. Cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets, 8(4):1-249, 2002. Google Scholar
  31. Junhao Gan and Yufei Tao. DBSCAN revisited: Mis-claim, un-fixability, and approximation. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 519-530, 2015. Google Scholar
  32. B. Gärtner. Fast and robust smallest enclosing balls. In European Symposium on Algorithms, 1999. Google Scholar
  33. Jonathan S. Greenfield. A proof for a quickhull algorithm, 1990. Google Scholar
  34. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. Tetrahedral meshing in the wild. ACM Trans. Graph., 37(4):60:1-60:14, July 2018. Google Scholar
  35. Alec Jacobson, Daniele Panozzo, et al. libigl: A simple C++ geometry processing library, 2018. https://libigl.github.io/. Google Scholar
  36. David G. Kirkpatrick and John D. Radke. A framework for computational morphology. In Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 217-248. Springer, 1985. Google Scholar
  37. Thomas Larsson, Gabriele Capannini, and Linus Källberg. Parallel computation of optimal enclosing balls by iterative orthant scan. Computers & Graphics, 56:1-10, 2016. Google Scholar
  38. D. Lebrun-Grandié, A. Prokopenko, B. Turcksin, and S. R. Slattery. ArborX: A performance portable geometric search library. ACM Trans. Math. Softw., 47(1), December 2020. Google Scholar
  39. Marco Livesu. cinolib: a generic programming header only C++ library for processing polygonal and polyhedral meshes. Transactions on Computational Science XXXIV, 2019. https://github.com/mlivesu/cinolib/. Google Scholar
  40. Kurt Mehlhorn and Stefan Näher. Leda: A platform for combinatorial and geometric computing. Commun. ACM, 38(1):96-102, January 1995. Google Scholar
  41. S. Näher and Daniel Schmitt. A framework for multi-core implementations of divide and conquer algorithms and its application to the convex hull problem. In Canadian Conference on Computational Geometry (CCCG), 2008. Google Scholar
  42. F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM, 20(2):87-93, February 1977. Google Scholar
  43. Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985. Google Scholar
  44. Octavian Procopiuc, Pankaj K Agarwal, Lars Arge, and Jeffrey Scott Vitter. Bkd-tree: A dynamic scalable kd-tree. In International Symposium on Spatial and Temporal Databases, pages 46-65, 2003. Google Scholar
  45. Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons. Reducing contention through priority updates. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures, pages 152-163, 2013. Google Scholar
  46. Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Aapo Kyrola, Harsha Vardhan Simhadri, and Kanat Tangwongsan. Brief announcement: The problem based benchmark suite. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures, pages 68-70, 2012. Google Scholar
  47. Daniel Sieger and Mario Botsch. The polygon mesh processing library, 2020. http://www.pmp-library.org. Google Scholar
  48. D Srikanth, Kishore Kothapalli, R Govindarajulu, and P Narayanan. Parallelizing two dimensional convex hull on NVIDIA GPU and Cell BE. In International Conference on High Performance Computing (HiPC), pages 1-5, 2009. Google Scholar
  49. Ayal Stein, Eran Geva, and Jihad El-Sana. Cudahull: Fast parallel 3d convex hull on the gpu. Computers & Graphics, 36(4):265-271, 2012. Applications of Geometry Processing. Google Scholar
  50. Min Tang, Jie yi Zhao, Ruo feng Tong, and Dinesh Manocha. GPU accelerated convex hull computation. Shape Modeling International (SMI) Conference, 36(5):498-506, 2012. Google Scholar
  51. Stanley Tzeng and John D Owens. Finding convex hulls using quickhull on the GPU. arXiv preprint arXiv:1201.2936, 2012. Google Scholar
  52. Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. Fast parallel algorithms for Euclidean minimum spanning tree and hierarchical spatial clustering. In Proceedings of the International Conference on Management of Data, pages 1982-1995, 2021. Google Scholar
  53. Emo Welzl. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, pages 359-370, 1991. 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 About DROPS Imprint Privacy Contact