Kinetic smallest enclosing disk: Difference between revisions

Revision as of 18:48, 19 May 2012

Latest revision as of 23:29, 18 October 2015

(25 intermediate revisions by 8 users not shown)

Line 1:

A '''kinetic smallest enclosing disk''' data structure is a [[kinetic data structure]] that maintains the [[Smallest_circle_problemSmallest circle problem|smallest enclosing disk]] of a set of moving points.

{{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 the farthest point delaunay triangulation of the point set to maintain the kineticsmallest enclosing disk.<ref name="DEGS10" /><\ref>. The farthest-point delaunay[[Delaunay triangulation]] is the [[dual_Duality (Projectiveprojective Geometrygeometry)|dual]] of the [[Voronoi diagram#Higher-order Voronoi diagrams#Farthest|farthest-point Voronoi diagram|]]. It is known that if the farthest-point Voronoidelaunay diagramtriangulation 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 an 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.

* '''[[Kinetic data structure#Performance|Locality]]:''' A point can be involved in <math>\Theta(n)</math> certificates. Therefore, this data structure is not local.

* '''[[Kinetic data structure#Performance|Compactness]]:''' This data structure requires O(n) certificates total, and thus is compact.

* '''[[Kinetic data structure#Performance|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> events is an open problem.<ref name="DEGS10" />

The

== Approximate 2D ==

The smallest enclosing disk of a set of n moving points can be [[Approximation_algorithm#Epsilon_terms|ε-approximated]] by a kinetic data structure that processes <math>O(1/\epsilon^{5/2})</math> events and requires <math>O((n/\sqrt{\epsilon})\log n)</math> time total.<ref name="AH01" />

== 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" /><\ref>

== References ==

{{Reflist| refrefs=

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

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{157148–157, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.

<\/ref>

}}

[[Category:Kinetic data structures]]

[[Category:Computational geometry]]