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. While many efficient algorithms were known in the static case, they proved hard to kinetize, so new static algorithms were developed to solve this problem.

2D case

Approach 1

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

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...

s. Consider a hexagon and partition it into six

equilateral triangle In geometry, an equilateral triangle is a triangle in which all three sides have the same length. In the familiar Euclidean geometry, an equilateral triangle is also equiangular; that is, all three internal angles are also congruent to each oth ...

s, and then create a Delaunay triangulation based on each equilateral triangle, as each one is a convex shape. The union of these six Delaunay triangulations, so called Equilateral Delaunay graph (EDG), is a supergraph for the

nearest neighbor graph The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from ''p'' to ''q'' whenever ''q'' is a near ...

(NNG); the endpoints of the edge with minimum length in EDG gives the closest pair. It is straightforward to maintain Delaunay triangulations based on convex shapes. Given the EDG over time, by creating a kinetic tournament tree over the edges of the EDG, one can easily maintain the closest pair. 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.

Approach 2

The second kinetic approach is based on the following observations.

Divide and conquer

If the space around a point is divided angularly into six "wedges", each wide, the closest point to is the closest of the closest points in each of the wedges. The rest of this article will focus on the "main" wedges (those bisected by the x-axis), and symmetrical arguments will apply to the other wedges after rotating the plane by .

Matched points

Points and are said to be "matched" if they are the closest points to each other. Clearly, the closest pair of points is a matched pair. Consider points and , such that is to the left of and lies in the wedge centered at described above. If is the closest point to , then must be the closest point (in this wedge) to , in the x-direction. Thus, the set of pairs of closest points (within this wedge) in the x-direction is a superset of the set of pairs of closest points.

Construction

# Map each point ''p''=(''x'', ''y'') in the set ''P'' to a new point , forming the set ''P' '' of transformed points. Note that for a point , the points in the "main" wedges have and coordinates either larger or smaller than in this new coordinate system. # Sort the points by ''x'',''u'' and ''v'' coordinates, and store them in

kinetic sorted list A kinetic sorted list is a kinetic data structure for maintaining a list of points under motion in sorted order. It is used as a kinetic predecessor data structure, and as a component in more complex kinetic data structures such as kinetic clos ...

s. # Construct a 2D

range tree In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by J ...

''T'' on the points in . For every node ''w'' in the primary tree, let ''T''(''w'') be the secondary tree associated with ''w''. This range tree will be used to identify the points in the "main" wedge for a point . # For every node ''w'' in the primary tree, and every node ''e'' in ''T''(''w''), calculate the pair (''w'', ''e'') = (''b'', ''r''), where ''b'' (or ''r'') is defined to be the point with maximum (or minimum) x-coordinate in the left (or right) subtree of ''e''. Let be the set of (''w'', ''e'') for all pairs ''w'', ''e'' in ''T''. This is a superset of the set of pairs of closest points (within the main wedge). # Build a

kinetic priority queue A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum (or minimum) priority element (key-value pair) when the priority of every element is changing as a continuous func ...

on the pairs in , with priorities determined by the distance (measured in the original co-ordinate system) between the points in the pair. # Repeat the above steps for the plane rotated , to get kinetic priority queues on and respectively. The closest pair of points in ''P'' corresponds to the minimum of the minimums obtained from the three priority queues above.

Maintenance

Certificate failures can occur in the priority queues and the sorted lists. Swaps in the ordering of the points will cause changes to ''T'' (which will take time), and may cause insertions/deletions in the priority queues. Note that the number of changes to the sets as defined above need not be a constant number. However, any pair that starts or stops being matched as a result of the ordering of p and q changing must contain p and/or q, and hence there are only a constant number of matched pairs that must be inserted into/deleted from the priority queues. It is ok to only update these matched pairs since, by definition, only matched pairs have a chance of being the closest pair.

Analysis

This KDS is: * Responsive: takes time to process an event *

Local Local may refer to: Geography and transportation * Local (train), a train serving local traffic demand * Local, Missouri, a community in the United States * Local government, a form of public administration, usually the lowest tier of administrat ...

: since each point is present in a constant number of kinetic sorted lists and kinetic priority queues, locality follows from the locality of those structures *

Compactness In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...

: compactness follows from the compactness of the kinetic sorted lists and kinetic priority queues * Efficient: every swap in the sorted lists causes a constant number of insertions and deletions in the kinetic priority queues. Assuming the motion of the points is pseudo-algebraic, there are a polynomial number of swaps, and hence a polynomial number of events are processed by this KDS, making it efficient This approach can be used to maintain the closest pair in higher dimensions.

References

{{Reflist, refs= Kinetic data structures Geometric data structures