I/O-Efficiently Pruning Dense Spanners

摘要

Given a geometric graph G = (S, E) in R~d with constant dilation t, and a positive constant ε, we show how to construct a (1 + ε)-spanner of G with O(|S|) edges using O(sort(|E|)) I/O operations.