Kinetic closest pair

Last updated February 13, 2022

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,^[1] 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 triangulations.^[2]

Consider a hexagon and partition it into six equilateral triangles, 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 (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.^[3]^[4]

Divide and conquer

If the space around a point $p$ is divided angularly into six "wedges", each $60°$ wide, the closest point to $p$ 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 $\pm60°$ .

Matched points

Points $p$ and $q$ 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 $p$ and $q$ , such that $p$ is to the left of $q$ and $q$ lies in the wedge centered at $p$ described above. If $p$ is the closest point to $q$ , then $q$ must be the closest point (in this wedge) to $p$ , 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 $p' = (u, v) = (x + \sqrt 3 y, y - \sqrt 3 x)$ , forming the set P' of transformed points. Note that for a point $p$ , the points in the "main" wedges have $u$ and $v$ coordinates either larger or smaller than $p'$ in this new coordinate system.
Sort the points by x,u and v coordinates, and store them in kinetic sorted lists.
Construct a 2D range tree T on the points in $P'$ . 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 $w$ .
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 $Π(0)$ 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 on the pairs in $Π(0)$ , 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 $\pm60°$ , to get kinetic priority queues on $Π(1)$ and $Π(-1)$ 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 $O (log 2 n)$ 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 $O (log 2 n)$ time to process an event
Local: 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: 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.

Related Research Articles

In mathematics and computational geometry, a Delaunay 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 of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of $points in the plane or higher-dimensional Euclidean space. It connects the points by a system of line segments, so that any two points can reach each other along a path through the line segments, and it selects line segments that minimize the sum of the Euclidean distances between directly-connected pairs of points.$

A triangulation of a set of points $in the Euclidean space is a simplicial complex that covers the convex hull of, and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.$

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 nearest neighbor of p, a point whose distance from p is minimum among all the given points other than p itself.

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points $and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set.$

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Introduced by Vuillemin (1980) in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence.

Leonidas John Guibas is the Paul Pigott Professor of Computer Science and Electrical Engineering at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories.

In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β.

In graph theory, the rectilinear minimum spanning tree (RMST) of a set of n points in the plane is a minimum spanning tree of that set, where the weight of the edge between each pair of points is the rectilinear distance between those two points.

In computer science, a ball tree, balltree or metric tree, is a space partitioning data structure for organizing points in a multi-dimensional space. The ball tree gets its name from the fact that it partitions data points into a nested set of intersecting hyperspheres known as "balls". The resulting data structure has characteristics that make it useful for a number of applications, most notably nearest neighbor search.

In the theory of cluster analysis, the nearest-neighbor chain algorithm is an algorithm that can speed up several methods for agglomerative hierarchical clustering. These are methods that take a collection of points as input, and create a hierarchy of clusters of points by repeatedly merging pairs of smaller clusters to form larger clusters. The clustering methods that the nearest-neighbor chain algorithm can be used for include Ward's method, complete-linkage clustering, and single-linkage clustering; these all work by repeatedly merging the closest two clusters but use different definitions of the distance between clusters. The cluster distances for which the nearest-neighbor chain algorithm works are called reducible and are characterized by a simple inequality among certain cluster distances.

A kinetic data structure is a data structure used to track an attribute of a geometric system that is moving continuously. For example, a kinetic convex hull data structure maintains the convex hull of a group of $moving points. The development of kinetic data structures was motivated by computational geometry problems involving physical objects in continuous motion, such as collision or visibility detection in robotics, animation or computer graphics.$

A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements where the priority is changing as a continuous function of time. As a type of kinetic priority queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property – if $B$ is a child node of $A$ , then the priority of the element in $A$ must be higher than the priority of the element in $B$ . This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue to maintain certificate failure times.

A kinetic triangulation data structure is a kinetic data structure that maintains a triangulation of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve motion planning, such as video games, virtual reality, dynamic simulations and robotics.

A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum priority element when the priority of every element is changing as a continuous function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.

A kinetic width data structure is a kinetic data structure which maintains the width of a set of moving points. In 2D, the width of a point set is the minimum distance between two parallel lines that contain the point set in the strip between them. For the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the width of a point set that is responsive, compact and efficient.

A kinetic smallest enclosing disk data structure is a kinetic data structure that maintains the smallest enclosing disk of a set of moving points.

Kinetic minimum box is a kinetic data structure to maintain the minimum bounding box of a set of points whose positions change continuously with time. For points moving in a plane, the kinetic convex hull data structure can be used as a basis for a responsive, compact and efficient kinetic minimum box data structure.

A kinetic Euclidean minimum spanning tree is a kinetic data structure that maintains the Euclidean minimum spanning tree (EMST) of a set P of n points that are moving continuously.

References

↑ Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747–756. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link)
↑ Rahmati, Z.; King, V.; Whitesides, S. (2013). Kinetic data structures for all nearest neighbors and closest pair in the plane. Proceedings of the 29th ACM Symposium on Computational Geometry. pp. 137–144. doi:10.1145/2462356.2462378.
↑ Basch, Julien; Guibas, Leonidas J.; Zhang, Li (1997). Proximity problems on moving points. Proceedings of the 13th ACM Symposium on Computational Geometry. pp. 344–351.
↑ Agarwal, P.K.; Kaplan, Haim; Sharir, Micha (November 2008). "Kinetic and dynamic data structures for closest pair and all nearest neighbors". Transactions on Algorithms (TALG). 5 (1).

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[mobile-1] Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747–756. Retrieved May 17, 2012.{{cite conference}}: CS1 maint: multiple names: authors list (link)

[Rahmati-2] Rahmati, Z.; King, V.; Whitesides, S. (2013). Kinetic data structures for all nearest neighbors and closest pair in the plane. Proceedings of the 29th ACM Symposium on Computational Geometry. pp. 137–144. doi:10.1145/2462356.2462378.

[BGZ-3] Basch, Julien; Guibas, Leonidas J.; Zhang, Li (1997). Proximity problems on moving points. Proceedings of the 13th ACM Symposium on Computational Geometry. pp. 344–351.

[AKS-4] Agarwal, P.K.; Kaplan, Haim; Sharir, Micha (November 2008). "Kinetic and dynamic data structures for closest pair and all nearest neighbors". Transactions on Algorithms (TALG). 5 (1).

[1]

[2]

[3]

[4]