Kinetic data structure: Difference between revisions

Revision as of 15:25, 17 May 2012

Latest revision as of 22:54, 19 May 2023

(47 intermediate revisions by 24 users not shown)

Line 1:

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

{{Userspace draft|source=ArticleWizard|date=May 2012}} <!-- Please leave this line alone! -->

{{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">Leonidas{{Cite J.thesis |last1=Basch Guibas,|first1=Julien |title=Kinetic Data Structures, 2001.|publisher=Stanford University [|url=http://graphicswww.stanfordbasch.eduorg/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf]</ref>phdthesis 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.|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 |year=2014|hdl=1828/5627 }}</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.

==Overview==

Kinetic data structures are used on systems werewhere there areis a set of values that are changing as a function of time, in a known fashion. So the system has some values, and for each value <math>v</math>, it is known that <math>v=f(t)</math>.

Kinetic data structures allow queries on a system at the current virtual time <math>t</math>, and two additional operations:

*'''<math>\textrm{advance}(t)</math>''': This advancesAdvances the system to time <math>t</math>.

*'''<math>\textrm{change}(v,f(t))</math>''': SetAlters the trajectory of value <math>v</math> to <math>f(t)</math>, as of the current time.

Additional operations may be supported. For example, kinetic data structures are often used with a set of points. In this case, the structure typically allowallows points to be inserted and deleted.

==Contrast with traditional data structures==

A kinetic data structure allows the values stored in it to change continuously with time. In principle, this can be approximated by sampling the position of the points at fixed intervals of time, and deleting and re-inserting each point into a "static" (traditional) data structure. However, such an approach is vulnerable to oversampling or undersampling, depending on what interval of time is used, and can also be wasteful of computational resources.

==Certificates Approachapproach==

The following general approach can be used to construct kinetic data structures: <ref>{{Citation
| first = Leonidas J.
| last = Guibas,
| author-link = Leonidas J. Guibas
| contribution = Kinetic Data Structures --: A State of the Art Report, 1998</ref>

| contribution-url = http://graphics.stanford.edu/courses/cs428-03-spring/Papers/readings/CollaborativeProcessing/g-kds.pdf

#Store a data structure on the system at the current time t. This data structure allows queries on the system at the current virtual time.

| title = Robotics: The Algorithmic Perspective (Proceedings of the 3rd Workshop on the Algorithmic Foundations of Robotics)

#Augment the data structure with certificates. Certificates are conditions under which the data structure is accurate. The certificates are all true now, and the data structure will only cease to be accurate when one of the certificates is no longer true.

| editor-first = Pankaj K.

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

| editor-last = Agarwal

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

| editor2-first = Lydia E.

#To advance to time t, look at the certificate with the lowest failure time from the priority queue. If the certificate fails before time t, 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 t. If the certificate with the lowest failure time in the priority queue fails after time, then all certificates are true at time t so the data structure can correctly answer queries at time t.

| editor2-last = Kavraki

===Types of Events===

| editor3-first = Matthew T.

An event is considered internal if the property maintained by the kinetic data structure does not change when the event occurs. An event is considered external if the property maintained by the data structure changes when the event occurs.

| editor3-last = Mason

| publisher = A K Peters/CRC Press

| isbn = 978-1-56881-081-2

| pages = 191–209

| year = 1998

}}</ref>

# Store a data structure on the system at the current time <math>t</math>. This data structure allows queries on the system at the current virtual time.

# Augment the data structure with certificates. Certificates are conditions under which the data structure is accurate. The certificates are all true now, and the data structure will only cease to be accurate when one of the certificates is no longer true.

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

===PerformanceTypes of events===

Certificate failures are referred to as "events". An event is considered internal if the property maintained by the kinetic data structure does not change when the event occurs. An event is considered external if the property maintained by the data structure changes when the event occurs.

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{polylog}(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{polylog}(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{polylog}(n))</math> or <math>O(n^\epsilon)</math> for arbitrarily small <math>\epsilon</math>.

==Performance==

==Types of Trajectories==

When using the certificates approach, there are four measures of performance. We say a quantity is small if it is a [[polylogarithmic function]] of <math>n</math>, or is <math>O(n^\epsilon)</math> for arbitrarily small <math>\epsilon</math>, where <math>n</math> is the number of objects:

====Responsiveness====

TheResponsiveness is 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 thean update is <math>O(\textrm{polylog}(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 responsivelocal if the maximum number of certificates any one value is involved with is <math>O(\textrm{polylog}(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 the number of certificates it uses is <math>O(n \textrmoperatorname{Polylogpolylog}( n))</math> or <math>O(n^{1+\epsilon})</math> for arbitrarily small <math>\epsilon</math>. (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 changedchanges as time is advanced to <math>t=\infty</math>. A kinetic data structure is said to be efficient if this ratio is <math>O(\textrm{polylog}(n))</math> or <math>O(n^\epsilon)</math> for arbitrarily small <math>\epsilon</math>.

===Types of Events=trajectories==

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 41 ⟶ 67:

==Examples==

*[[Kinetic Predecessortournament]]

*[[Kinetic Heapsorted list]]

*[[Kinetic Convex Hullheap]]

*[[Kinetic Closestconvex Pairhull]]

*[[Kinetic closest pair]]

*[[Kinetic minimum spanning tree]]

*[[Kinetic Euclidean minimum spanning tree]]

== References ==

{{Reflist}}

== External links ==

<!--- Categories --->

[[Category:ArticlesKinetic createddata via the Article Wizardstructures]]