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 the farthest point delaunay triangulation of the point set to maintain the smallest enclosing disk.^[1] 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 circumcircle of this triangle is the smallest enclosing disk. Otherwise, the smallest enclosing disk has the diameter of the point set as its diameter. Thus, by maintaining the kinetic diameter of the point set, the farthest-point delaunay triangulation, and whether or not the farthest-point delaunay triangulation has an acute triangle, the smallest enclosing disk can be maintained. This data structure is responsive and compact, but not local or efficient:^[1]

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

Approximate 2D

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

Higher dimensions

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

References

1 2 3 4 Erik D. Demaine, Sarah Eisenstat, Leonidas J. Guibas, André Schulz, Kinetic Minimum Spanning Circle, 2010.
↑ Pankaj K. Agarwal and Sariel Hal-Peled. Maintaining approximate extent measures of moving points. In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 148–157, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.

This article is issued from Wikipedia - version of the 10/18/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.