Cardinal directions between spatial objects: the pairwise-consistency problem. (English) Zbl 1094.68678

Cicerone, Serafino; Di Felice, Paolino

Inf. Sci. 164, No. 1-4, 165-188 (2004).

Summary: The paper formalizes an open problem (called by the authors the pairwise-consistency problem) which is relevant in the context of cardinal directions among extended objects, proposes an efficient algorithmic solution for it, discusses the implementation of the algorithm and briefly reports the numerical results obtained by running the code.

MSC:

68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
68U35	Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
68P15	Database theory

Keywords:

Cardinal relations; Spatial relations; Spatial queries; Data quality; Spatial database systems; Geographical information systems

Software:

LEDA

References:

[1]	Cicerone, S.; Di Felice, P., Cardinal relations between regions with a broad boundary, (8th ACM Symposium on Advances in Geographic Information Systems (GIS’00) (2000), ACM Press), 15-20
[2]	Clementini, E.; Di Felice, P., Spatial operators, ACM SIGMOD Record, 29, 3, 31-38 (2000)
[3]	Clementini, E.; Di Felice, P.; Hernández, D., Qualitative representation of positional information, Artificial Intelligence, 95, 2, 317-356 (1997) · Zbl 0894.68143
[4]	A.U. Frank, Qualitative spatial reasoning about cardinal directions, in: D. Mark, D. White (Eds.), Autocarto 10, 1991, pp. 148-167; A.U. Frank, Qualitative spatial reasoning about cardinal directions, in: D. Mark, D. White (Eds.), Autocarto 10, 1991, pp. 148-167
[5]	Freksa, C., Using orientation information for qualitative spatial reasoning, (Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Lecture Notes in Computer Science, vol. 639 (1992), Springer-Verlag), 162-178
[6]	R.K. Goyal, M.J. Egenhofer, Cardinal directions between extended spatial objects, IEEE Transactions on Knowledge and Data Engineering, in press. Available from <http://www.spatial.maine.edu/ max/RJ36.html; R.K. Goyal, M.J. Egenhofer, Cardinal directions between extended spatial objects, IEEE Transactions on Knowledge and Data Engineering, in press. Available from <http://www.spatial.maine.edu/ max/RJ36.html · Zbl 0997.68632
[7]	Goyal, R. K.; Egenhofer, M. J., Consistent queries over cardinal directions across different levels of detail, (11th International Workshop on Database and Expert System Applications (DEXA’00) (2000), IEEE Press), 876-880
[8]	Goyal, R. K.; Egenhofer, M. J., Similarity of cardinal directions, (7th International Symposium on Spatial and Temporal Databases (SSTD’01). 7th International Symposium on Spatial and Temporal Databases (SSTD’01), Lecture Notes in Computer Science, vol. 2121 (2001), Springer-Verlag), 36-55 · Zbl 0997.68632
[9]	Skiadopoulos, S.; Koubarakis, M., Composing cardinal direction relations, (7th International Symposium on Spatial and Temporal Databases (SSTD’01). 7th International Symposium on Spatial and Temporal Databases (SSTD’01), Lecture Notes in Computer Science, vol. 2121 (2001), Springer-Verlag), 299-317 · Zbl 0997.68574
[10]	(Kuper, G.; Libkin, L.; Paredaens, J., Constraint Databases (1999), Springer-Verlag) · Zbl 0935.00022
[11]	Mehlhorn, K.; Näher, S., The LEDA Platform of Combinatorial and Geometric Computing (1999), Cambridge University Press · Zbl 0976.68156
[12]	Papadias, D.; Egenhofer, M. J.; Sharma, J., Hierarchical reasoning about direction relations, (4th International Symposium on Advances in Geographic Information Systems (ACM GIS’96) (1996), ACM Press), 105-112
[13]	Papadias, D.; Sellis, T., Qualitative representation of spatial knowledge in two-dimensional space, VLDB Journal, 3, 4, 479-516 (1994)
[14]	Peuquet, D. J.; Zhan, C.-X, An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane, Pattern Recognition, 20, 1, 65-74 (1987)
[15]	PHP: the official web site. Available from <http://www.php.net; PHP: the official web site. Available from <http://www.php.net
[16]	Samet, H., The Design and Analysis of Spatial Data Structures (1989), Addison-Wesley Pub. Co
[17]	Shekhar, S.; Liu, X., Direction as a spatial object: a summary of results, (6th International Symposium on Advances in Geographic Information Systems (ACM GIS’98) (1998), ACM Press), 69-75
[18]	The algorithm described in this paper. Available from <http://www.ing.univaq.it/ cicerone/consistency/; The algorithm described in this paper. Available from <http://www.ing.univaq.it/ cicerone/consistency/