Path integral molecular dynamics: Difference between revisions
en>Darth Vader's Dad m →References: Added external link to mentioned web site |
|||
| Line 1: | Line 1: | ||
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] | |||
<!--- Categories ---> | |||
[[Category:Articles created via the Article Wizard]] | |||
[[Category:Kinetic data structures]] | |||
[[Category:Triangulation (geometry)]] | |||
Latest revision as of 19:27, 19 April 2013
A Kinetic Triangulation data structure is a kinetic data structure that maintains a 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.[1]
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 estimated by ,[2] thus the number of changes to any triangulation is also lower bounded by . Finding any triangulation scheme that has a near-quadratic bound on the number of discrete changes is an important open problem.[1]
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,[3] and the best currently known upper bound is .
There is a kinetic data structure that efficiently maintains the Delaunay triangulation of a set of moving points,[4] in which the ratio of the total number of events to the number of external events is .
Other triangulations
Kaplan et al. developed a randomized triangulation scheme that experiences an expected number of external events, where is the maximum number of times each triple of points can become collinear, , and is the maximum length of a Davenport-Schinzel sequence of order s + 2 on n symbols.[1]
Pseudo-triangulations
There is a kinetic data structure (due to Agarwal et al.) which maintains a pseudo-triangulation in events total.[5] All events are external and require time to process.
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- 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.[1]
- ↑ 1.0 1.1 1.2 Cite error: Invalid
<ref>tag; no text was provided for refs namedmicha - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedconvex hull - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs nameddelaunay hardness - ↑ 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.
- ↑ 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. [2]