An Efficient Construction of Yao-Graph in Data-Distributed Settings
Preprint
Abstract
A sparse graph that preserves an approximation of the shortest paths between all pairs of points in a plane is called a geometric spanner. Using range trees of sublinear size, we design an algorithm in massively parallel computation (MPC) model for constructing a geometric spanner known as Yao-graph. This improves the total time and the total memory of existing algorithms for geometric spanners from subquadratic to near-linear.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Sampling and sparsification for approximating the packedness of trajectories and detecting gatheringsInternational Journal of Data Science and Analytics, 2022
- Communication Steps for Parallel Query ProcessingJournal of the ACM, 2017
- Approximating geometric bottleneck shortest pathsComputational Geometry, 2004