Kinetic smallest enclosing disk: Difference between revisions

Revision as of 17:36, 19 May 2012

Revision as of 18:47, 19 May 2012

Line 1:

{{Userspace draft|source=ArticleWizard|date=May 2012}} <!-- Please leave this line alone! -->

A '''kinetic smallest enclosing disk''' data structure is a [[kinetic data structure]] that maintains the [[Smallest_circle_problem|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 <ref name="DEGS10"><\ref>. The farthest-point delaunay triangulation is the [[dual_(Projective Geometry)]] of the [[Voronoi diagram#Higher-order Voronoi diagrams#Farthest-point Voronoi diagram|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.<ref name="DEGS10"><\ref>

== References ==

{{Reflist}} ref=

<ref name ="DEGS10">

Erik D. Demaine, Sarah Eisenstat, Leonidas J. Guibas, Andre Schulz, Kinetic Minimum Spanning Circle, 2010. [http://www.ams.sunysb.edu/~jsbm/fwcg10/papers/25.pdf]

<\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>

}}