Use of rational numbers in the design of robust geometric primitives for three-dimensional spatial database systems

ABSTRACT

A necessary step in the implementation of three-dimensional spatial data types for spatial database systems and GIS is the development of robust geometric primitives. The authors have previously shown the need for 3D spatial data types and rigorously defined them. In this paper, we propose a set of 3D geometric primitives that can be used to implement them robustly. We provide for their robustness by specifying them using rational numbers. In the discretization of space, the developers of two-dimensional spatial data types have used simplicial complexes, realms or dual grids to produce robustness, but extending any of these to 3D is not adequate. Furthermore, rational number theory is sufficiently developed to apply to 3D implementation primitives. Efforts are lacking, however, in the field of spatial databases to show that spatial operations involving 3D spatial data types are closed under rational arithmetic. We therefore define four geometric primitives using rational numbers: point, segment, facet and solid which correspond to 0D, 1D, 2D and 3D spatial objects respectively. Also, we compare the rational specification of 3D primitives to the discretization methods used in 2D. Finally, we show that intersections involving these primitives have rational closure. We therefore conclude that use of rational numbers in the design of geometric primitives provides for a robust implementation of three-dimensional spatial data types.

REFERENCES

• 1: C. Batut, K. Belabas, D. Bernardi, H. Cohen, and M. Olivier. User's Guide to PARI/GP. The PARI Group, urlhttp://pari.math.u-bordeaux.fr/, 2000.
• 2: C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, Efficient exact geometric computation made easy, Proceedings of the fifteenth annual symposium on Computational geometry, p.341-350, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304988]
• 3: Jose Antonio Cotelo Lema , Ralf Hartmut Güting, Dual Grid: A New Approach for Robust Spatial Algebra Implementation, Geoinformatica, v.6 n.1, p.57-76, March 2002 [doi>10.1023/A:1013768114909 ]
• 4: Freddy Dumortier , Marc Gyssens , Luc Vandeurzen , Dirk Van Gucht, On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.68-77, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263670]
• 5: Floris Geerts , Bart Kuijpers, Linear approximation of planar spatial databases using transitive-closure logic, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-135, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335215]
• 6: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 7: J. Keyser, J. M. Rojas, and K. Ouchi. The Exact Rational Univariate Representation and Its Application. In D. Duffa, R. Janardan, and M. Smid, editors, AMS/DIMACS Volume on Computer Aided Design and Manufacturing. American Mathematical Society/Center for Discrete Mathematics and Computer Science, 2005.
• 8: M. Schneider. Spatial Data Types for Database Systems - Finite Resolution Geometry for Geographic Information Systems, volume LNCS 1288. Springer-Verlag, Berlin Heidelberg, 1997.
• 9: Markus Schneider , Brian E. Weinrich, An abstract model of three-dimensional spatial data types, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032234]
• 10: M. Tommila. apfloat: A C++ High Performance Arbitrary Precision Arithmetic Package. World Wide Web, urlhttp://www.apfloat.org/apfloat/2.40/, February 22 2003.
• 11: Chee-Keng Yap, Towards exact geometric computation, Computational Geometry: Theory and Applications, v.7 n.1-2, p.3-23, Jan. 1997 [doi>10.1016/0925-7721(95)00040-2 ]
• 12: S. Zlatanova, On 3D Topological Relationships, Proceedings of the 11th International Workshop on Database and Expert Systems Applications, p.913, September 06-08, 2000

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
3D spatial data types, GIS, discrete model, geometric primitives, rational numbers, spatial database