Content deleted Content added
No edit summary |
No edit summary |
||
Line 5:
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"></ref>. 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 is has the diameter of the point set as it's diameter. Thus, by maintaining the [[kinetic diameter]] of the point set, the 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>
* '''[[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"></ref>
Line 27:
}}
[[Category:Kinetic data structures]]
[[Category:Computational geometry]]
| |||