Output-sensitive well-separated pair decompositions for dynamic point sets
Eunhui Park, David M. Mount · 2013
The well-separated pair decomposition (WSPD) is a fundamental structure in computational geometry. Given a set P of n points in d-dimensional space and a positive separation parameter s, an s-WSPD is a concise representation of all the O(n2) pairs of P requiring only O(sdn) storage. The WSPD has numerous applications in spatial data processing, such as computing spanner graphs, minimum spanning trees, shortest-path oracles, and statistics on interpoint distances. We consider the problem of maintaining a WSPD when points are inserted to or deleted from P.