Kinetic data structure: Difference between revisions

Revision as of 09:12, 30 September 2016

Latest revision as of 22:54, 19 May 2023

(6 intermediate revisions by 6 users not shown)

Line 1:

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

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

</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>A '''kinetic data structure''' is a [[data structure]] used to track an attribute of a geometric system that is moving continuously.<ref name=MAAbam"JBasch">{{Cite thesis |last1=AbamBasch |first1=Mohammad AliJulien |title=NewKinetic Data Structures and Algorithms for Mobile Data |publisher=EindhovenStanford University of Technology |url=http://repositorywww.tuebasch.nlorg/630204phdthesis |year=20071999}}

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

</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 38 ⟶ 40:

# Compute the failure time of each certificate, the time when it will cease to be true.

# Store the certificates in a priority queue, keyed by their failure times

# To advance to time <math>t</math>, look at the certificate with the lowest failure time from the priority queue. If the certificate fails before time <math>t</math>, pop it from the queue and fix the data structure so it is accurate at the time of failure, and update the certificates. Repeat this until the certificate with the lowest failure time in the priority queue fails after time <math>t</math>. If the certificate with the lowest failure time in the priority queue fails after time <math>t</math>, then all certificates are true at time <math>t</math> so the data structure can correctly answer queries at time <math>t</math>.

===Types of events===

Line 58 ⟶ 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 75 ⟶ 77:

== References ==

{{Reflist}}

== External links ==

<!--- Categories --->

[[Category:Articles created via the Article Wizard]]

[[Category:Kinetic data structures]]