Abstract
The ROSE algebra, defined earlier, is a system of spatial data types for use in spatial database systems. It offers data types to represent points, lines, and regions in the plane together with a comprehensive set of operations; semantics of types and operations have been formally defined. Values of these data types have a quite general structure, e.g. an object of type regions may consist of several polygons with holes. All ROSE objects are realm-based which means all points and vertices of objects lie on an integer grid and no two distinct line segments of any two objects intersect in their interior. In this paper we describe the implementation of the ROSE algebra, providing data structures for the types and new realm-based geometric algorithms for the operations. The main techniques used are (parallel) traversal of objects, plane-sweep, and graph algorithms. All algorithms are analyzed with respect to their worst case time and space requirements. Due to the realm properties, these algorithms are relatively simple, efficient, and numerically completely robust. All data structures and algorithms have indeed been implemented in the ROSE system; the Modula-2 source code is freely available from the authors for study or use.
This work was supported by the DFG (Deutsche Forschungsgemeinschaft) under grant Gu 293/1-2.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.V., J.E. Hopcroft, and J.D. Ullman, Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.
Becker, L., and R.H. Güting, Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Transactions on Database Systems 17 (1992), 247–303.
Greene, D., and F. Yao, Finite-Resolution Computational Geometry. Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, 143–152.
Güting, R.H., Gral: An Extensible Relational Database System for Geometric Applications. Proc. of the 15th Intl. Conf. on Very Large Databases (Amsterdam, The Netherlands), 1989, 33–44.
Güting, R.H., Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization. Proc. ACM SIGMOD Conf. (Washington, USA), 1993, 277–286.
Güting, R.H., An Introduction to Spatial Database Systems. VLDB Journal 3, 4 (1994) (Special Issue on Spatial Database Systems), 357–399.
Güting, R.H., and M. Schneider, Realms: A Foundation for Spatial Data Types in Database Systems. Proc. of the 3rd Intl. Symposium on Large Spatial Databases (Singapore), 1993, 14—35.
Güting, R.H., and M. Schneider, Realm-Based Spatial Data Types: The ROSE Algebra. Femuniversität Hagen, Informatik-Report 141, 1993. To appear in the VLDB Journal.
Karlsson, R.G., and J.I. Munro, Proximity on a Grid. Proc. of the 2nd Symp. on Theoretical Aspects of Computer Science, Springer-Verlag, LNCS 182, 1985, 187–196.
Karlsson, R.G., and M.H. Overmars, Scanline Algorithms on a Grid. BIT 28 (1988), 227–241.
Karlsson, R.G., and M.H. Overmars, Normalized Divide-and-Conquer: A Scaling Technique for Solving Multi-Dimensional Problems. Information Processing Letters 26 (1988), 307–312.
Keil, J.M., and D.G. Kirkpatrick, Computational Geometry on Integer Grids. Proc. of the 19th Annual Allerton Conference on Communication, Control, and Computing, 1981, 41–50.
Klaeren, H.A., Algebraische Spezifikation. Springer Verlag, Berlin, 1983.
Mehlhorn, K., Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry. Springer Verlag, 1984.
Müller, H., Rastered Point Location. Proc. Workshop on Graphtheoretic Concepts in Computer Science, Trauner Verlag, 1985, 281–293.
Orenstein, J., and F. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. on Software Engineering 14 (1988), 611–629.
Overmars, M.H., Efficient Data Structures for Range Searching on a Grid. Journal of Algorithms 9 (1988), 254–275.
Overmars, M.H., New Algorithms for Computer Graphics. Advances in Computer Graphics, Eurographics Seminars, Springer Verlag, 1988, 3–19.
Overmars, M.H., Computational Geometry on a Grid: An Overview. Theoretical Foundations for Computer Graphics and CAD, Springer Verlag, 1988, 167–184.
Preparata F.P., and M.I. Shamos, Computational Geometry. Springer Verlag, 1985.
de Ridder, T., The ROSE System. Modula-2 Program System (Source Code). Fernuniversität Hagen, Praktische Informatik IV, Software Report 1, 1995. Available as a LaTeX file for printing and/or as a compressed collection of ASCII files.
Yao F.F., Computational Geometry. Algorithms and Complexity. Handbook of Theoretical Computer Science, vol. A, Elsevier Science Publishers B.V., 1992, 343–389.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Güting, R.H., de Ridder, T., Schneider, M. (1995). Implementation of the ROSE algebra: Efficient algorithms for realm-based spatial data types. In: Egenhofer, M.J., Herring, J.R. (eds) Advances in Spatial Databases. SSD 1995. Lecture Notes in Computer Science, vol 951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60159-7_14
Download citation
DOI: https://doi.org/10.1007/3-540-60159-7_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60159-3
Online ISBN: 978-3-540-49536-9
eBook Packages: Springer Book Archive