ParGeo is now being maintained at https://github.com/ParAlg/ParGeo
Pargeo is being developted at MIT. It hosts a growing set of multi-core implementations for parallel algorithms in computational geometry:
- Graph Generators
- Euclidean MST
- K-Nearest Neighbor Graph
- Planar Beta-Skeleton
- Planar Delaunay Graph
- Planar Gabriel Graph
- T-Spanner
- Spatial Query
- K-Nearest Neighbor
- Range Search
- Closest Pair
- 2D & 3D Z-Order Sort
- Planar Delaunay Triangulation
- Well-Separated Pair Decomposition
Pargeo runs on any modern x86-based multicore machines. To compile, it requires g++ 5.4.0 or later. The build system is CMake.
Pargeo uses the parlaylib, a wonderful library developed at CMU for multi-core parallel programming. It and other dependencies are included in the project as submodules - initialize them before compiling the code:
git submodule init
git submodule update
Starting from the project root directory:
mkdir build
cd build
cmake ..
make -j # this will take a while
After the build completes, navigate to <project-root>/build/executable, where the executables are generated. Running ./<executable> in the terminal displays short usage instructions. As an example, to compute the Euclidean MST of a point data set <data-file>, input the following, and the MST edges will be written to edges.txt.
./emst -o edges.txt <data-file>
Example data sets can be found here. Pargeo automatically parses CSV-like point data files with or without header, as long as the delimiters (space, comma, etc) in between numbers are one character each in length.