Path integral molecular dynamics

2013-04-19T17:27:57Z

128.59.74.3: /* Theory behind the method */

A '''Kinetic Triangulation''' data structure is a [[kinetic data structure]] that maintains a [[triangulation (geometry)|triangulation]] of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve [[motion planning]], such as video games, virtual reality, dynamic simulations and robotics.<ref name="micha"/>

==Choosing a triangulation scheme==
The efficiency of a kinetic data structure is defined based on the ratio of the number of internal events to external events, thus good runtime bounds can sometimes be obtained by choosing to use a triangulation scheme that generates a small number of external events.
For simple [[affine motion]] of the points, the number of discrete changes to the [[convex hull]] is [[big O notation#Family of Bachmann–Landau notations|estimated by]] <math>\Omega(n^2)</math>,<ref name="convex hull"/> thus the number of changes to any triangulation is also lower bounded by <math>\Omega(n^2)</math>. Finding any triangulation scheme that has a near-quadratic bound on the number of discrete changes is an important open problem.<ref name="micha"/>

===Delaunay triangulation===
The [[Delaunay triangulation]] seems like a natural candidate, but a tight analysis of the number of discrete changes that will occur to the Delaunay triangulation (external events) is one of the hardest problems in computational geometry,<ref name="delaunay hardness"/> and the best currently known upper bound is <math>O(n^3)</math>.

There is a kinetic data structure that [[Kinetic data structure#Performance|efficiently]] maintains the Delaunay triangulation of a set of moving points,<ref>Gerhard Albers, Leonidas J. Guibas, Joseph S. B. Mitchell, and Thomas Roos. Voronoi diagrams of moving points. Int. J. Comput. Geometry Appl., 8(3):365{380, 1998.</ref> in which the ratio of the total number of events to the number of external events is <math>O(1)</math>.

===Other triangulations===
Kaplan et al. developed a [[randomized algorithm|randomized]] triangulation scheme that experiences an expected number of <math>O(n^2 \beta_{s+2}(n) \log^2 n)</math> external events, where <math>s</math> is the maximum number of times each triple of points can become collinear, <math>\beta_{s+2}(q) = \frac{\lambda_{s+2}(q)}{q}</math>, and <math>\lambda_{s+2}(q)</math> is the maximum length of a [[Davenport-Schinzel sequence]] of order s + 2 on n symbols.<ref name="micha"/>

===Pseudo-triangulations===
There is a kinetic data structure (due to Agarwal et al.) which maintains a [[pseudo-triangulation]] in <math>O(n^22^{\sqrt{\log n\log\log n}})</math> events total.<ref>Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, and Li Zhang. Deformable free-space tilings for kinetic collision detection. I. J. Robotic Res., 21(3):179{198, 2002. [http://research.microsoft.com/en-us/um/people/lzha/papers/pset-j.pdf]</ref> All events are [[Kinetic data structure#Certificates Approach|external]] and require <math>O(\lg n)</math> time to process.

== References ==
{{Reflist|refs=
<ref name="micha">
{{cite conference | url=http://www.math.tau.ac.il/~michas/triank.pdf | title=A Kinetic Triangulation Scheme for Moving Points in The Plane | publisher=ACM | accessdate=May 19, 2012 | author=Kaplan, Haim; Rubin, Natan; Sharir, Micha | year=2010 | month=June |conference=SCG}}
</ref>
<ref name="convex hull">
{{cite book | title=Davenport-Schinzel sequences and their geometric applications | publisher=, Cambridge University Press | author=Sharir, M,; Agarwal, P.K. | year=1995 | location=New York}}
</ref>
<ref name="delaunay hardness">
{{cite web | url=http://www.cs.smith.edu/~orourke/TOPP/ | title=The Open Problems Project | accessdate=May 19, 2012 | author=Demaine, E.D.; Mitchell, J. S. B. ; O’Rourke, J.}}
</ref>
}}
*Pankaj K. Agarwal, Julien Basch, Mark de Berg, Leonidas J. Guibas, and John Hershberger. Lower bounds for kinetic planar subdivisions. In SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry, pages 247{254, New York, NY, USA, 1999. ACM.[http://research.microsoft.com/en-us/um/people/lzha/papers/pset-j.pdf]



[[Category:Articles created via the Article Wizard]]
[[Category:Kinetic data structures]]
[[Category:Triangulation (geometry)]]

formulasearchengine - User contributions [en]

Path integral molecular dynamics