Loading...
Please wait, while we are loading the content...
Similar Documents
Kinetic Data Structures: Animating Proofs Through Time
| Content Provider | CiteSeerX |
|---|---|
| Author | Basch, Julien Comba, João Guibas, Leonidas J. Hershberger, John |
| Abstract | Kinetic Data Structures (KDS for short) are a new class of data structures aimed at keeping track of attributes of interest in systems of moving objects [1,2]. In this video we illustrate the principles of KDS design in the context of some classical geometric problems,such as the calculation of the convex hull or closest pair of moving points in the plane. In an ordinary simulation the positions of the points are advanced by a fixed time step,and then the attribute of interest in incrementally recomputed. Since the combinatorial structure of the attribute changes irregularly,it is quite difficult to select a time-step size that avoids both oversampling and undersampling the system. Unlike such fixed step methods,a kinetic data structure performs an event-driven simulation where only events relevant to the attribute of interest are generated and processed. The result is a simulation that is always accurate and with a computation cost close to the minimum possible. This video presents animations for and contains the description of a few two-dimensional kinetic geometric algorithms: • Convex Hull ([1]): We compute a static convex hull for a set of points as follows: we divide the points randomly into two groups (red and blue),compute the convex hull of each group recursively,and then merge the two hulls. During this process,we create certificates for the hull’s correctness. At the top level each certificate is an oriented triangle connecting the red and blue sub-hulls — a certificate triangle verifies that one of its vertices is not on the convex hull. Altogether,the certificates from all levels of the recursion prove the correctness of the convex hull. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Oriented Triangle Ordinary Simulation Fixed Time Step Hull Correctness Static Convex Hull Event-driven Simulation Certificate Triangle Verifies Fixed Step Method Attribute Change Two-dimensional Kinetic Geometric Algorithm Top Level Blue Sub-hulls Kds Design Kinetic Data Structure Time-step Size Animating Proof Classical Geometric Problem |
| Content Type | Text |
