skip to main content
10.1145/1097064.1097088acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
Article

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

Published: 04 November 2005 Publication History

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, and S. Schirra. Efficient Exact Geometric Computation Made Easy. Proc. of the 15th Annual Symp. on Computational Geometry, pp. 341--350, Miami Beach, Florida, USA, June 13-16 1999.
[3]
J. A. Cotelo Lema and R. H. Güting. Dual Grid: A New Approach for Robust Spatial Algebra Implementation. GeoInformatica, 6(1):57--76, 2002.
[4]
F. Dumortier, M. Gyssens, L. Vandeurzen, and D. Van Gucht. On the Decidability of Semi-Linearity for Semi-Algebraic Sets and Its Implications for Spatial Databases. Proc. of the 16th ACM SIGACT - SIGMOD - SIGART Symp. on Principles of Database Systems, pp. 68--77, Tucson, Arizona, USA, 1997.
[5]
F. Geerts and B. Kuijpers. Linear Approximation of Planar Spatial Databases Using Transitive-Closure Logic. Proc. of the 19th ACM SIGMOD - SIGACT - SIGART Symp. on Principles of Database Systems, pp. 126--135, 2000.
[6]
R. H. Güting. An Introduction to Spatial Database Systems. VLDB Journal, 3(4):357--399, 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]
M. Schneider and B. E. Weinrich. An Abstract Model of Three-Dimensional Spatial Data Types. Proc. of the 12th ACM Int. Symp. on Advances in Geographic Information Systems (ACM GIS 2004), pp. 67--72, 2004.
[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]
C. K. Yap. Towards Exact Geometric Computation. Computer Geometry: Theory and Applications, 7(1-2):3--23, 1997.
[12]
S. Zlatanova. On 3D Topological Relationships. Int. Workshop on Database and Expert System Applications, pp. 913--919, 2000.

Cited By

View all
  • (2017)LandXML Encoding of Mixed 2D and 3D Survey Plans with Multi-Level TopologyISPRS International Journal of Geo-Information10.3390/ijgi60601716:6(171)Online publication date: 12-Jun-2017
  • (2015)Fast exact parallel map overlay using a two-level uniform gridProceedings of the 4th International ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data10.1145/2835185.2835188(45-54)Online publication date: 3-Nov-2015

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systems
      November 2005
      306 pages
      ISBN:1595931465
      DOI:10.1145/1097064
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 04 November 2005

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. 3D spatial data types
      2. GIS
      3. discrete model
      4. geometric primitives
      5. rational numbers
      6. spatial database

      Qualifiers

      • Article

      Conference

      CIKM05
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 257 of 1,238 submissions, 21%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 13 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2017)LandXML Encoding of Mixed 2D and 3D Survey Plans with Multi-Level TopologyISPRS International Journal of Geo-Information10.3390/ijgi60601716:6(171)Online publication date: 12-Jun-2017
      • (2015)Fast exact parallel map overlay using a two-level uniform gridProceedings of the 4th International ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data10.1145/2835185.2835188(45-54)Online publication date: 3-Nov-2015

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media