An operation-independent approach to extend 2D spatial operations to 3D and moving objects

ABSTRACT

It has been pointed out repeatedly that spatial operations must be extended to include support for 3D and moving objects. The attempt to code by hand each spatial operation for each data type (e.g., static 2D, moving 2D, static 3D, and moving 3D) is forbidding and has led to specific solutions for particular purposes. In this paper, we have advocated an operation-independent approach to extend 2D spatial operations to 3D and moving objects. The approach is based on implementation of the concepts of n-dimensional geometry through definition of transformations between domains called "lifting". It is explained via some sample spatial operations and then the implementation results for convex hull computation are represented.

REFERENCES

• 1: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 2: Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis, Spatio-Temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases, Geoinformatica, v.3 n.3, p.269-296, September 1999 [doi>10.1023/A:1009805532638]
• 3: Andrew U. Frank, One Step up the Abstraction Ladder: Combining Algebras - From Functional Pieces to a Whole, Proceedings of the International Conference on Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science, p.95-107, August 25-29, 1999
• 4: Frank, A. U. and Gruenbacher, A. 2001. Temporal Data: 2nd order concepts lead to an algebra for spatio-temporal objects. In Proceedings of Workshop on Complex Reasoning on Geographical Data, 1 December, 2001, Cyprus.
• 5: Farid Karimipour , Mahmoud R. Delavar , Andrew U. Frank, A Mathematical Tool to Extend 2D Spatial Operations to Higher Dimensions, Proceeding sof the international conference on Computational Science and Its Applications, Part I, June 30-July 03, 2008, Perugia, Italy [doi>10.1007/978-3-540-69839-5_12]
• 6: Karmipour F., Delavar, M. R., and Rezayan, H. 2006. Formalization of Moving Objects' Spatial Analysis Using Algebraic Structures. In Proceedings of Extended Abstracts of GIScience 2006 Conference, Munster, Germany, IfGI Prints Vol. 28, pp. 105--111.
• 7: Karimipour, F., Delavar, M. R., Frank, A. U., and Rezayan, H. 2005. Point in Polygon Analysis for Moving Objects. In Proceedings of the 4th Workshop on Dynamic & Multidimensional GIS, Gold, C. (ed.), 5--8 September, 2005, Pontypridd, Wales, UK, ISPRS Working Group II/IV, 68--72.
• 8: Karimipour, F. 2005. Logical Formalization of Spatial Analyses of Moving Objects Using Algebraic Structures, M.Sc. Thesis (in Persian with English abstract), College of Engineering, University of Tehran, Iran.
• 9: Knuth, D. E., 1992 Axioms and Hulls, Lecture Notes in Computer Science, Vol. 606, Springer-Verlag.
• 10: F. William Lawvere , Stephen H. Schanuel, Conceptual mathematics: a first introduction to categories, Buffalo Workshop Press, Buffalo, NY, 1991
• 11: Ledoux H. 2008. The Kinetic 3D Voronoi Diagram: A Tool for Simulating Environmental Processes, in Oosterom, P. V., Zlatanova, S., Penninga, F. and Fendel, E. (eds.) Advances in 3D Geo Information Systems. Proceeding of the 2nd International Workshop on 3D Geoinformation, December 12--14, 2007, Delft, the Netherlands, Lecture Notes in Geoinformation and Cartography, Springer-Verlag, 361--380.
• 12: Hugo Ledoux, Computing the 3D Voronoi Diagram Robustly: An Easy Explanation, Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering, p.117-129, July 09-11, 2007 [doi>10.1109/ISVD.2007.10]
• 13: Ledoux, H. 2006. Modelling three-dimensional fields in geoscience with the Voronoi diagram and its dual. PhD thesis, School of Computing, University of Glamorgan, Pontypridd, Wales, UK.
• 14: MacLane, S. and Birkhoff, G. 1999 Algebra, 3^rd Edition. AMS Chelsea Publishing.
• 15: Mir Abolfazl Mostafavi , Christopher Gold , Maciej Dakowicz, Delete and insert operations in Voronoi/Delaunay methods and applications, Computers & Geosciences, v.29 n.4, p.523-530, May 2003 [doi>10.1016/S0098-3004(03)00017-7]
• 16: Bengt Nordström , Kent Petersson , Jan M. Smith, Programming in Martin-Lo¨f's type theory: an introduction, Clarendon Press, New York, NY, 1990
• 17: Oosterom, P. V., Zlatanova, S., Penninga, F., and Fendel, E. (eds.) 2008 Advances in 3D Geo Information Systems, Proceeding of the 2nd International Workshop on 3D Geoinformation, December 12--14, 2007, Delft, the Netherlands, Lecture Notes in Geoinformation and Cartography, Springer-Verlag.
• 18: Peyton Jones, S. and Hughes, J. 1999. Haskell 98: A Non-Strict, Purely Functional Language. From http://www.haskell.org/onlinereport/ (accessed June, 2008).
• 19: Simon Thompson, The Haskell: The Craft of Functional Programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 20: Chorochronos Project 2004. http://www.dbnet.ece.ntua.gr/~choros/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Algebraic language theory

General Terms:
Algorithms, Languages, Theory

Keywords:
3D GIS, functor, lifting, moving objects, spatial operations