Kinetic smallest enclosing disk

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

2D

In 2 dimensions, the best known kinetic smallest enclosing disk data structure uses farthest point delaunay triangulation of the point set to maintain the kinetic . The farthest-point Delaunay triangulation is the dual of the farthest-point Voronoi diagram. It is known that if the farthest-point delaunay triangulation of a point set contains an acute triangle, the smallest enclosing disk of this triangle is the smallest enclosing disk. Otherwise, the smallest enclosing disk is the diameter of the point set. Thus, by maintaining kinetic diameter, farthest-point delaunay triangulation, and whether or not the farthest-point delaunay triangulation has a acute triangle, the smallest enclosing disk can be maintained. This data structure is responsive and compact, but not local or efficient:

• Responsiveness: This data structure requires $O(\log ^{2}n)$ time to process each certificate failure, and thus is responsive.
• Locality: A point can be involved in $\Theta (n)$ certificates. Therefore, this data structure is not local.
• Compactness: This data structure requires O(n) certificates total, and thus is compact.
• Efficiency: This data structure has $O(n^{3+\epsilon })$ events total.(for all $\epsilon >0$ The best known lower bound on the number of changes to the smallest enclosing disk is $\Omega (n^{2})$. Thus the efficiency of this data structure, the ratio of total events to external events, is $O(n^{1+\epsilon })$.

The existence of kinetic data structure that has $o(n^{3+\epsilon })$ events is an open problem.

Approximate 2D

The smallest enclosing disk of a set of n moving points can be ε-approximated by a kinetic data structure that process $O(1/\epsilon ^{5/2})$ events and requires $O((n/{\sqrt {\epsilon }})\log n)$ time total.

Higher dimensions

In dimensions higher than 2, efficiently maintaining the smallest enclosing sphere of a set of moving points is a open problem.

References

{{Reflist ref= }}