Algorithms for dynamic closest pair and n-body potential fields
Paul B. Callahan, S. Rao Kosaraju · 1995
We present a general technique for dynamizing certain problems posed on point sets in Euclidean space for any fixed dimension d. This technique applies to a large class of structurally similar algorithms, presented previously by the authors, that make use of the well-separated pair decomposition. We prove efficient worst-case complexity for maintaining such computations under point insertions and deletions, and apply the technique to several problems posed on a set P containing n points. In particular, we show how to answer a query for any point x that returns a constant-size set of points, a subset of which consists of all points in P that have x as a nearest neighbor. We then show how to use such queries to maintain the closest pair of points in P . We also show how to dynamize the fast multipole method, a technique for approximating the potential field of a set of point charges. All our algorithms use the algebraic model that is standard in computational geometry, and have worst-ca...