License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.88
URN: urn:nbn:de:0030-drops-170265
Go to the corresponding LIPIcs Volume Portal

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

ParGeo: A Library for Parallel Computational Geometry

LIPIcs-ESA-2022-88.pdf (1 MB)


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.

BibTeX - Entry

  author =	{Wang, Yiqiu and Yesantharao, Rahul and Yu, Shangdi and Dhulipala, Laxman and Gu, Yan and Shun, Julian},
  title =	{{ParGeo: A Library for Parallel Computational Geometry}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{88:1--88:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-170265},
  doi =		{10.4230/LIPIcs.ESA.2022.88},
  annote =	{Keywords: Computational Geometry, Parallel Algorithms, Libraries}

Keywords: Computational Geometry, Parallel Algorithms, Libraries
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022
Supplementary Material: Software (Source Code):

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