Kinetic closest pair

A kinetic closest pair data structure is a kinetic data structure that maintains the closest pair of points, given a set P of n points that are moving continuously with time in a metric space.

The simplest kinetic approach for maintenance of the closest pair is to use variants of the Delaunay triangulations.

This closest pair KDS is efficient, amortized responsive, and compact, but in general is not local.

The following approach presents a local KDS for maintenance of the closest pair.

This KDS is: This approach can be used to maintain the closest pair in higher dimensions.