Kinetic data structure: Difference between revisions

Revision as of 12:47, 13 December 2021

Latest revision as of 22:54, 19 May 2023

(One intermediate revision by one other user not shown)

Line 1:

{{Short description|dataData structures used to track continuously moving geometric bodies}}

{{Use American English|date = April 2019}}

A '''kinetic data structure''' is a [[data structure]] used to track an attribute of a geometric system that is moving continuously.<ref name="JBasch">{{Cite thesis |last1=Basch |first1=Julien |title=Kinetic Data Structures |publisher=Stanford University |url=http://www.basch.org/phdthesis |year=1999}}

Line 60:

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 changes as time is advanced to <math>t=\infty</math>. A kinetic data structure is said to be efficient if this ratio is small.

==Types of Trajectoriestrajectories==

The performance of a certain kinetic data structure may be analyzed for certain types of trajectories. Typically, the following types of trajectories are considered:

*'''Affine''':(Linear functions) <math>f(t)=at+b</math>