Cardinal relations between regions with a broad boundary

ABSTRACT

Despite the innovative relevance of the results about spatial relations today available, the expressiveness of spatial query languages needs to be pushed further significantly in order to cope with the complexity of spatial entities. In particular, more research is necessary in order to support queries against data with uncertainty. In connection with cardinal directions, the best method today available is the Boolean, 3 × 3 direction-relation matrix proposed very recently by Goyal and Egenhofer. Our paper extends such a method to the case of regions with a broad boundary by introducing a 4-value, 5 × 5 direction-relation matrix. Furthermore, the present contribution studies the notion of consistency for a direction-relation matrix and proposes a set of conditions which are necessary and sufficient for assessing consistency.

REFERENCES

• 1: [1] E. Clementini and P. Di Felice. An Algebraic Model for Spatial objects with Indeterminate Boundaries, chapter 11, pages 155-169. GISDATA. Taylor & Francis, (P. A. Burrogh and A. U. Frank Eds), 1996.
• 2: Eliseo Clementini , Paolino Di Felice , Daniel Hernández, Qualitative representation of positional information, Artificial Intelligence, v.95 n.2, p.317-356, Sept. 1997 [doi>10.1016/S0004-3702(97)00046-5]
• 3: [3] A. G. Cohn and N. M. Golts. The 'Egg-Yolk' representation of regions with indeterminate boundary, chapter 12, pages 171-187. GISDATA. Taylor & Francis, (P. A. Burrogh and A. U. Frank Eds), 1996.
• 4: Alberto Del Bimbo , Pietro Pala, Visual Image Retrieval by Elastic Matching of User Sketches, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.121-132, February 1997 [doi>10.1109/34.574790]
• 5: [5] M. J. Egenhofer, Query processing in spatial-query-by-sketch. Journal of Visual Languages and Computing, 8(4):403-424, 1997.
• 6: [6] M. J. Egenhofer and J. R. Herring. Categorizing binary topological relations between regions, lines, and points in geographic databases. Technical Report, Department of Surveying Engineering, University of Maine, 1990.
• 7: Martin Erwig , Markus Schneider, Vague Regions, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.298-320, July 15-18, 1997
• 8: [8] A. U. Frank. Qualitative spatial reasoning about cardinal directions. In D. Mark and D. White, editors, Autocarto 10, pages 148-167, 1991.
• 9: Christian Freksa, Using Orientation Information for Qualitative Spatial Reasoning, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.162-178, September 21-23, 1992
• 10: [10] R. K. Goyal and M. J. Egenhofer, Cardinal directions between extended spatial objects. IEEE Transactions on Knowledge and Data Engineering, 2000. In press.
• 11: Gabriel Kuper , Jan Paredaens , Leonid Libkin, Constraint Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 12: Dimitris Papadias , Timos Sellis, Qualitative representation of spatial knowledge in two-dimensional space, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 13: Dimitris Papadias , Yannis Theodoridis , Timos K. Sellis, The Retrieval of Direction Relations using R-trees, Proceedings of the 5th International Conference on Database and Expert Systems Applications, p.173-182, September 07-09, 1994
• 14: D. J. Peuquet , Ci-Xiang Zhang, An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane, Pattern Recognition, v.20 n.1, p.65-74, 1987 [doi>10.1016/0031-3203(87)90018-5]
• 15: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: Markus Schneider, Uncertainty Management for Spatial Data in Databases: Fuzzy Spatial Data Types, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.330-351, July 20-23, 1999
• 17: Shashi Shekhar , Xuan Liu, Direction as a spatial object: a summary of results, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.69-75, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288706]