Out-of-order event processing in kinetic data structures
Pages 624 - 635
Abstract
We study the problem of designing kinetic data structures (KDS's for short) when event times cannot be computed exactly and events may be processed in a wrong order. In traditional KDS's this can lead to major inconsistencies from which the KDS cannot recover. We present more robust KDS's for the maintenance of two fundamental structures, kinetic sorting and tournament trees, which overcome the difficulty by employing a refined event scheduling and processing technique. We prove that the new event scheduling mechanism leads to a KDS that is correct except for finitely many short time intervals. We analyze the maximum delay of events and the maximum error in the structure, and we experimentally compare our approach to the standard event scheduling mechanism.
References
[1]
P. K. Agarwal, L. Arge, and J. Erickson. Indexing moving points. J. Comput. Syst. Sci. , 66:207-243, 2003.
[2]
P. K. Agarwal, J. Gao, and L. J. Guibas. Kinetic medians and kd-trees. In Proc. 10th European Sympos. on Algorithms , pages 5-16, 2002.
[3]
P. K. Agarwal, L. J. Guibas, J. Hershberger, and E. Veach. Maintaining the extent of a moving point set. Discrete Comput. Geom. , 26(3):353-374, 2001.
[4]
P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. J. ACM , 51(4):606-635, 2004.
[5]
G. Alexandron, H. Kaplan, and M. Sharir. Kinetic and dynamic data structures for convex hulls and upper envelopes. In Proc. 9th Intl. Workshop on Data Structures , pages 269-281, 2005.
[6]
J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. J. Algorithms , 31:1-28, 1999.
[7]
J. Basch, L. J. Guibas, and L. Zhang. Proximity problems on moving points. In Proc. 13th ACM Sympos. Comput. Geom. , pages 344-351, 1997.
[8]
The CGAL Library. http://www.cgal.org/.
[9]
G. Collins and A. Akritas. Polynomial real root isolation using Descarte's rule of signs. In Proc. 3rd ACM Sympos. Symbol. Algebra. Comput. , pages 272-275, 1976.
[10]
The Core Library. http://www.cs.nyu.edu/exact/.
[11]
S. Fortune. Progress in computational geometry. In R. Martin, editor, Directions in Geometric Computing , pages 81-128. Information Geometers Ltd., 1993.
[12]
S. Funke, C. Klein, K. Mehlhorn, and S. Schmitt. Controlled perturbation for Delaunay triangulations. In Proc. 16th ACM-SIAM Sympos. Discrete Algorithms , pages 1047-1056, 2005.
[13]
L. J. Guibas. Algorithms for tracking moving objects. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry . CRC Press, 2nd edition, 2004.
[14]
L. J. Guibas and M. Karavelas. Interval methods for kinetic simulation. In Proc. 15th Annu. ACM Sympos. Comput. Geom. , pages 255-264, 1999.
[15]
L. J. Guibas, M. Karavelas, and D. Russel. A computational framework for handling motion. In Proc. 6th Workshop on Algorithm Engineering and Experiments , pages 129-141, 2004.
[16]
L. J. Guibas and D. Russel. An empirical comparision of techniques for updating Delaunay triangulations. In Proc. 20th Annu. Sympos. Comput. Geom. , pages 170-179, 2004.
[17]
D. Halperin and C. Shelton. A perturbation scheme for spherical arrangements with application to molecular modeling. Comput. Geom. Theory Appl. , 10:273-287, 1998.
[18]
N. Jacobson. Basic Algebra I . W. H. Freeman, New York, 2nd edition, 1985.
[19]
V. Milenkovic and E. Sacks. An approximate arrangement algorithm for semi-algebraic curves. In Proc. 22nd Annu. Sympos. Comput. Geom. , pages 237-246, 2006.
[20]
S. Schirra. Robustness and precision issues in geometric computation. In J. R. Sack and J. Urrutia, editors, Handbook of Computational Geometry , pages 597-632. Elsevier Science, 2000.
[21]
C. Yap. Robust geometric computation. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry . CRC Press, 2nd edition, 2004.
Index Terms
- Out-of-order event processing in kinetic data structures
Recommendations
Out-of-Order Event Processing in Kinetic Data Structures
We study the problem of designing kinetic data structures (KDS's for short) when event times cannot be computed exactly and events may be processed in a wrong order. In traditional KDS's this can lead to major inconsistencies from which the KDS cannot ...
Soft kinetic data structures
SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithmsWe introduce the framework of soft kinetic data structures (SKDS). A soft kinetic data structure is an approximate data structure that can be used to answer queries on a set of moving objects with unpredictable motion. We analyze the quality of a soft ...
A package for exact kinetic data structures and sweepline algorithms
In this paper we present a package for implementing exact kinetic data structures built on objects which move along polynomial trajectories. We discuss how the package design was influenced by various considerations, including extensibility, support for ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 11 September 2006
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in