Kinetic smallest enclosing disk: Difference between revisions

Revision as of 18:49, 19 May 2012

Revision as of 19:14, 19 May 2012

Line 3:

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[[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 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:<ref name="DEGS10"></ref>

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

The

* '''Locality:''' A point can be involved in <math>\Theta(n)</math> 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 <math>O(n^{3+\epsilon})</math> events total.(for all <math>\epsilon>0</math> The best known lower bound on the number of changes to the smallest enclosing disk is <math>\Omega(n^2)</math>. Thus the efficiency of this data structure, the ratio of total events to external events, is <math>O(n^{1+\epsilon})</math>.

The existence of kinetic data structure that has <math>o(n^{3+\epsilon})</math> is an open problem.<ref name="DEGS10"></ref>

== Approximate 2D ==