Kinetic data structure: Difference between revisions

Revision as of 08:16, 24 July 2019

Latest revision as of 22:54, 19 May 2023

(3 intermediate revisions by 3 users not shown)

Line 1:

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

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

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

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

</ref><ref name="LJGuibas">{{Citation |first=Leonidas J. |last=Guibas |author-link=Leonidas J. Guibas |contribution=Kinetic Data Structures |contribution-url=http://graphics.stanford.edu/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf |title=Handbook of Data Structures and Applications |editor-first=Dinesh P. |editor-last=Mehta |editor2-first=Sartaj |editor2-last=Sahni |publisher=Chapman and Hall/CRC |isbn=978-1-58488-435-4 |pages=23-1–23-18 |year=2001}}

</ref><ref name="MAAbam">{{Cite thesis |last1=Abam |first1=Mohammad Ali |title=New Data Structures and Algorithms for Mobile Data |publisher=Eindhoven University of Technology |url=http://repository.tue.nl/630204 |year=2007}}

</ref><ref name="ZRahmati">{{Cite thesis |last1=Rahmati |first1=Zahed |title=Simple, Faster Kinetic Data Structures |publisher=University of Victoria |urlyear=http://2014|hdl.handle.net/=1828/5627 |year=2014}}</ref>

For example, a [[kinetic convex hull]] data structure maintains the convex hull of a group of <math>n</math> moving points. The development of kinetic data structures was motivated by [[computational geometry]] problems involving physical objects in continuous motion, such as collision or visibility detection in robotics, animation or computer graphics.

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>

Line 77:

== References ==

{{Reflist}}

== External links ==

<!--- Categories --->

[[Category:Kinetic data structures]]