Kinetic data structure: Difference between revisions

Revision as of 15:21, 17 May 2012

Revision as of 15:21, 17 May 2012

Line 25:

When using this approach, there are four measures of performance:

====Responsiveness====

The worst case amount of time required to fix the data structure and augmenting certificates when a certificate fails. A kinetic data structure is responsive if the worst case amount of time required for the update is <math>O(\textrm{Polylogpolylog}(n))</math> or <math>O(n^\epsilon)</math> for arbitrarily small <math>\epsilon</math>.

====Locality====

The maximum number of certificates any one value is involved in. For structures involving moving points, this is that maximum number of certificates any one point is involved in. A kinetic data structure is responsive if the maximum number of certificates any one value is involved with is <math>O(\textrm{Polylogpolylog}(n))</math> or <math>O(n^\epsilon)</math> for arbitrarily small <math>\epsilon</math>.

====Compactness====

The maximum number of certificates used to augment the data structure at any time. A kinetic data structure is compact if <math>O(n \textrm{Polylog}(n))</math> or <math>O(n^{1+\epsilon})</math> for arbitrarily small <math>\epsilon</math>

====Efficiency====

The ratio of the worst case number of events that can occur when the structure is advanced to <math>t=\infty</math> to the worst case number of "necessary changes" to the data structure. The definition of "necessary changes" is problem dependent. For example, in the case of a kinetic data structure maintaining the kinetic hull of a set of moving points, the number of necessary changes would be the number of times the kinetic hull changed. A kinetic data structure is said to be efficient if this ratio is <math>O(\textrm{Polylogpolylog}(n))</math> or <math>O(n^\epsilon)</math> for arbitrarily small <math>\epsilon</math>.

==Types of Trajectories==