2023/08/29 by Sepideh Aghamolaei, Aghamolaei, Sepideh, Mohammad Ghodsi +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Data Management and Algorithms #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2308.15065
openalex publication_date 2023/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.