Kinetic smallest enclosing disk: Difference between revisions

Revision as of 01:33, 24 July 2012

Latest revision as of 23:29, 18 October 2015

(3 intermediate revisions by 3 users not shown)

Line 2:

== 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.<ref name="DEGS10" /> The farthest-point [[Delaunay triangulation]] is the [[Duality (projective geometry)|dual]] of the [[Voronoi diagram#Higher-order Voronoi diagrams|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 (data)|kinetic diameter]] of the point set, the farthest-point delaunay triangulation, and whether or not the farthest-point delaunay triangulation has aan acute triangle, the smallest enclosing disk can be maintained.

This data structure is responsive and compact, but not local or efficient:<ref name="DEGS10" />

* '''[[Kinetic data structure#Performance|Responsiveness]]:''' This data structure requires <math>O(\log^2 n)</math> time to process each certificate failure, and thus is responsive.

Line 14:

== Higher dimensions ==

In dimensions higher than 2, efficiently maintaining the smallest enclosing sphere of a set of moving points is aan open problem.<ref name="DEGS10" />

== References ==

{{Reflist| refs=

<ref name ="DEGS10">

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

</ref>

<ref name="AH01">