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 [1]. The farthest-point delaunay triangulation is the dual of the farthest-point Voronoi diagram.
The
Approximate 2D
Higher dimensions
In dimensions higher than 2, efficiently maintaining the smallest enclosing sphere of a set of moving points is a open problem.[1]
References
{{Reflist ref= <ref name ="DEGS10"> Erik D. Demaine, Sarah Eisenstat, Leonidas J. Guibas, Andre Schulz, Kinetic Minimum Spanning Circle, 2010. [1] <\ref> <ref name="AH01"> 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. <\ref> }}