Time-dependent affine triangulation of spatio-temporal data

ABSTRACT

In the geometric data model [6], spatio-temporal data are modelled as a finite collection of triangles that are transformed by time-dependent affinities. To facilitate querying and animation of spatio-temporal data, we present a <i>normal form</i> for data in the geometric data model. We propose an algorithm for constructing this normal form via a <i>spatio-temporal triangulation</i> of geometric data objects. This algorithm generates new geometric objects that form a partition both in space and in time. A particular property of the proposed partition is that it is invariant under time-dependent affine transformations, and hence independent of the coordinate system chosen when modelling the spatio-temporal data. We can show that our algorithm works correctly and has a polynomial time complexity (in the number of input triangles and the maximal degree of the transformation functions). We also discuss several possible applications of this spatio-temporal triangulation.

REFERENCES

• 1: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 2: J. Bochnak, M. Coste, and M.-F. Roy. Real Algebraic Geometry, volume 36 ofErgebenisse der Mathematik und ihrer Grenzgebiete. Folge 3. Springer-Verlag, 1998.
• 3: M. H. Böhlen, C. S. Jensen, and M. Scholl, editors. Spatio-Temporal Database Management, International Workshop STDBM 1999, volume 1678 ofLecture Notes in Computer Science. Springer-Verlag, 1999.
• 4: Mengchu Cai , Dinesh Keshwani , Peter Z. Revesz, Parametric Rectangles: A Model for Querying and Animation of Spatiotemporal Databases, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.430-444, March 27-31, 2000
• 5: C. X. Chen and C. Zaniolo. SQLST: A spatio-temporal data model and query language. In V. C. Laender, S. W. Liddle, editor,Conceptual Modeling, 19th International Conference on Conceptual Modeling (ER'00), volume 1920 of Lecture Notes in Computer Science, pages 96--111. Springer-Verlag, 2000.
• 6: Jan Chomicki , Sofie Haesevoets , Bart Kuijpers , Peter Revesz, Classes of Spatio-Temporal Objects and their Closure Properties, Annals of Mathematics and Artificial Intelligence, v.39 n.4, p.431-461, December 2003 [doi>10.1023/A:1026086723558]
• 7: Jan Chomicki , Peter Z. Revesz, A Geometric Framework for Specifying Spatiotemporal Objects, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning, p.41, May 01-02, 1999
• 8: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 9: Martin Erwig , Markus Schneider, Partition and Conquer, Proceedings of the International Conference on Spatial Information Theory: A Theoretical Basis for GIS, p.389-407, October 15-18, 1997
• 10: Andrew Frank , Stephane Grumbach , Ralf Hartmut Güting , Christian S. Jensen , Manolis Koubarakis , Nikos Lorentzos , Yannis Manolopoulos , Enrico Nardelli , Barbara Pernici , Hans-Jörg Schek , Michel Scholl , Timos Sellis , Babis Theodoulidis , Peter Widmayer, Chorochronos: a research network for spatiotemporal database systems, ACM SIGMOD Record, v.28 n.3, p.12-21, Sept. 1999 [doi>10.1145/333607.333609]
• 11: Floris Geerts , Sofie Haesevoets , Bart Kuijpers, A Theory of Spatio-Temporal Database Queries, Revised Papers from the 8th International Workshop on Database Programming Languages, p.198-212, September 08-10, 2001
• 12: Stéphane Grumbach , Philippe Rigaux , Luc Segoufin, Spatio-temporal data handling with constraints, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.106-111, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288712]
• 13: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 14: Marc Gyssens , Jan Van den Bussche , Dick Van Gucht, Complete geometric query languages, Journal of Computer and System Sciences, v.58 n.3, p.483-511, June 1999 [doi>10.1006/jcss.1999.1630]
• 15: Michiel Hagedoorn , Remco C. Veltkamp, Reliable and Efficient Pattern Matching Using an Affine Invariant Metric, International Journal of Computer Vision, v.31 n.2-3, p.203-225, April 1999 [doi>10.1023/A:1008022116857]
• 16: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 17: Bart Kuijpers , Jan Paredaens , Dirk Van Gucht, Towards a Theory of Movie Database Queries, Proceedings of the Seventh International Workshop on Temporal Representation and Reasoning (TIME'00), p.95, July 07-09, 2000
• 18: G. M. Nielson, A characterization of an affine invariant triangulation, Geometric modelling, Springer-Verlag, London, 1993
• 19: J. Paredaens, G. Kuper, and L. Libkin, editors. Constraint databases. Springer-Verlag, 2000.
• 20: Dieter Pfoser , Nectaria Tryfona, Requirements, definitions, and notations for spatiotemporal application environments, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.124-130, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288715]
• 21: Peter Revesz, Introduction to constraint databases, Springer-Verlag New York, Inc., New York, NY, 2002
• 22: L. Roberts. Machine perception of three-dimensional solids. J.T. Tippet, editor, Optical and Electro-optical Information Processing, 1965.
• 23: J. S. Y. Lamdan and H. Wolfson. Affine-invariant model-based object recognition. IEEE Journal of Robotics and Automation, 6:578--589, 1990.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design, Theory

Keywords:
spatio-temporal data models, triangulations