Kinetic data structure: Difference between revisions

Revision as of 15:30, 17 May 2012

Revision as of 15:31, 17 May 2012

Line 31:

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 small.

====Compactness====

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

====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 small.