摘要
随着空间数据库技术和地理信息系统(GIS)的不断发展和应用,空间推理的基础理论以及相应算法也在不断的创新和发展。目前空间推理主要分为拓扑关系推理、主方向关系推理和距离关系推理等。主方向关系推理是空间推理研究领域的重要分支,在空间推理的研究中有关主方向关系推理的研究越来越引起人们的注意。
方向关系模型在空间主方向关系推理的研究中是至关重要的。本文就已存在的方向关系模型进行了研究总结和比较,采用了比较适合空间关系运算的九方向关系模型。人们在空间方向关系的研究中常采用的空间数据类型分为“点”,“线”,“面”。“面”物体在空间数据库中常以最小边界矩形MBR(Minimum Bouding Rectangle)的方式表示。本文以物体的MBR为模型,利用区间代数及矩形代数理论,提出了一种基于MBR的主方向关系与矩形代数关系相结合的推理方法;同时利用方向关系矩阵表示物体MBR之间的方向关系,得到了基于方向关系矩阵的组合推理方法。
文中首先针对基于点物体的空间主方向推理进行讨论,在此基础上把点物体的主方向关系推理引深为基于物体的MBR主方向关系推理的问题。结合著名的Balbiani的矩形代数理论,提出了一种基于主方向物体MBR与矩形关系代数相结合的新模型。利用该模型可以很好地将矩形代数良好的计算性质应用于空间方向推理中,简化了方向推理地难度,实现了基于矩形代数的主方向关系一致性检验。
对于基于MBR方向关系组合推理的问题,本文使用方向关系矩阵表示物体MBR之间的方向关系。根据提出的一系列方向关系矩阵的性质和方向关系矩阵之间运算的定义、定理,提出了基于矩阵的方向关系之间的组合问题求解方法;针对基于MBR模型求解方向关系组合所存在的问题,提出了两种信息表示模型:深度方向关系矩阵和5×5方向关系矩阵,给出在5×5的方向关系矩阵上方向关系组合的扩展方法。
With the development and application of the spatial database technology and geographic information systems (GIS), the basic theories of spatial reasoning and the arithmetic corresponding to them are innovating and developing. At present, spatial reasoning mainly consists of topological relation reasoning, cardinal direction relation reasoning and distance relation reasoning, and so on. As an important division of the spatial reasoning, the cardinal direction relation reasoning has received more and more attentions.
The direction relation model is crucially important in the research for the spatial cardinal direction relation reasoning. This paper does some researches and comparisons on the existing direction relation models and uses the nine-direction relation model that is suitable for the operation on spatial relations. The spatial data types which are usually used in the research for the spatial direction relation contains“points”,“lines”and“polygons”.“Polygon”object is usually realized in form of the Minimum Bounding Rectangle (MBR) in the spatial database. This paper takes advantage of interval algebra and rectangle algebra theories. and brings forward a new reasoning method based on combination of the MBR model’s cardinal direction relation and rectangle algebra relation; And provides the composing method based on the direction relation matrix by using the direction relation matrix to denote the direction relations between the objects’MBRs.
This paper firstly discusses the spatial cardinal direction reasoning based on the point object, and then develops it into the cardinal direction relation reasoning problem based on the object’s MBR. Combining the famous Balbiani’s rectangle algebra theory, this paper provides a new model based on the combination of the cardinal direction object’s MBR and the rectangle relation algebra. Using the model, the nicer computing character of the rectangle algebra can be well applied in the spatial direction reasoning, which greatly reduced the difficulty of direction relations reasoning, and the consistency verification of the cardinal direction relation based on the rectangle algebra is implemented.
As for the direction relations composing problems based on the MBR, this paper uses direction relation matrix to denote the direction relation among the objects’MBRs. According to a series of the definitions put forward on the direction relation matrix’s character and computation, the theorem has provided the method to answer the problem on the composing between direction relations based on the matrix. Aim at the problem about the inconsistent of some composing results from the direction relation model based on the MBR ,this paper construct two information models :depth direction relations matrix and 5×5 direction relations matrix and put forward the method to answer the composing problem using 5×5 direction relation matrix.
引文
1 FRANK A. Qualitative Spatial Reasoning: Cardinal Directions as an Example[J]. International Journal of Geographic Information Systems, 1996, 10(3):269-290
2 Goyal R K. Similarity Assessment for Cardinal Directions between Extended Spatial Objects[D]. Maine: The University of Maine, 2000, 2:2-5
3 Olivier and K. Gapp, Eds. Representation and Processing of Spatial Expressions. Lawrence Erlbaum Associates, Publishers, Mahwah, NJ. 1998:7-8
4 Egenhofer and R. Franzosa. Point-Set Topological Spatial Relations. International Journal of Geographical Information Systems 1991, 5(2):161-174
5 Hong. Qualitative Distance and Direction Reasoning in geographic Space, Ph. D. Thesis, Department of Surveying Engineering, University of Maine, Orono, ME. 1994, 33-40
6 Byrne and P. Johnson-Laird. Spatial Reasoning. Journal of Memory and Language 1989, 28:564-575
7 Sharma. Integrated Spatial Reasoning in Geographic Information Systems: Combining Topology and Direction, Ph. D. Thesis, Department of Spatial Information Science and Engineering, University of Maine, Orono, ME. 1996:16-18
8 Peuquet and C.-X. Zhan. An Algorithm to Determin the Directional Relationship Between Arbitrarily-Shaped Polygons in the Plane. Pattern Recognition 1987, 20(1):65-74.
9 Abdelmoty. Modelling and Reasoning in Spatial Databases: A Deductive Object-Oriented Approach. Ph. D. thesis, Department of Computing and Electrical Engineering, Heriot-Watt University, Edinburgh, Scotland, 1995
10 Futch, D. Chin, M. McGranaghan and J.-G. Lay. Spatial-Linguistic Reasoning in LEI (Locality and Elevation Interpreter). Theories and Methods of Spatio-temporal Reasoning in Geographic Space, Pisa, Italy, A. Frank, I. Campari and U. Formentini, Eds., Lecture Notes in Computer Science, 1992,639:318-327
11 Gonzalez and R. Woods. Digital Image Processing. Addison-Wesley publishing Company, Reading, MA.1992:88-90
12 M.J. Egenhofer. Reasoning about binary topological relationships. in: Proceedings of SSD-91, 1991:143–160
13 A.U. Frank. Qualitative spatial reasoning about distances and directions in geographic space. J. Vis.Languages and Computing 3 (1992):343–371
14 Z. Cui, A.G. Cohn, D.A. Randell. Qualitative and topological relationships in spatial databases. in:Proceedings of SSD-93, 1993:296–315
15 B. Faltings. Qualitative spatial reasoning using algebraic topology. In: Proceedings of COSIT-95, in: Lecture Notes in Comput. Sci., Vol. 988, Springer, Berlin, 1995:101-111
16 D.A. Randell, Z. Cui, A. Cohn. A spatial logic based on regions and connection. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR’92), Morgan Kaufmann, San Mateo, CA, 1992:88
17 J. Renz, B. Nebel. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artificial Intelligence 108 (1–2) (1999): 69–123
18 D. Papadias, Y. Theodoridis, T. Sellis, M.J. Egenhofer. Topological relations in the world of minimum bounding rectangles: A study with R-trees. in: Proceedings of ACM SIGMOD-95, 1995:92–103
19 A.P. Sistla, C. Yu, R. Haddad. Reasoning about spatial relationships in picture retrieval systems. in: Proceedings of VLDB-94, 1994:570–581
20 B. Bennett. Logical representations for automated reasoning about spatial relations. PhD Thesis, School of Computer Studies, University of Leeds, 1997:78-88
21 R. Goyal, M.J. Egenhofer. Cardinal directions between extended spatial objects. IEEE Trans. Data Knowledge Engrg. (2000). Available at http://www.spatial.maine.edu/~max/RJ36.html
22 Ligozat G. Reasoning about cardinal directions. Journal of Visual Languages and Computing, 1998, 9(1):23~44
23 K. Zimmermann. Enhancing qualitative spatial reasoning—Combiningorientation and distance. In: Proceedings of COSIT-93, in: Lecture Notes in Comput. Sci., Vol. 716, Springer, Berlin, 1993:69–76
24 S. Shekhar, X. Liu, S. Chawla. An Object Model of Direction and Its Implications. GeoInformatica 3:4, 357-379 (1999), Kluwer Academic Publishers; A summary of results was among 5 best papers in Sixth International Symposium on Advances in Geographic Information System(1998)
25 Ligozat G F. Qualitative Triangulation for Spatial Reasoning. In: Frank A U, Campari I, eds, Spatial Information Theory: A Theoretical Basis for GIS. Berlin: Springer-Verlag, 1993:54-68
26 廖士中,高培焕,石纯一.定性空间推理的分层递阶框架.计算机研究与发展,2001,38(5):574-580
27 廖士中,石纯一.一种分层递阶的定性拓扑推理方法.软件学报,1999,10(5)
28 Yannis Theodorids, Dimitris Papadias (1998). Direction relations and two-dimensional range queries: optimization techniques. Elsevier Science B.V.[24]
29 Spiros Skiadopoulos, Manolis Koubarakis. Composing cardinal direction relations. Artificial Intelligence 152(2004):143-171
30 J.Nievergelt, H.Hinterberger and K.C.Sevcik. The Grid File: An Adaptable symmetric multikey file structure. ACM Transactions on Database Systems, 1984, 9:38-71
31 Raphael A. Finkel, Jon Louis Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf, 1974, 4:1-9
32 Antonin Guttman. R-trees: A Dynamic Index Structure for Spatial Searching. Beatrice Yormark. ACM SIGMOD Proceedings of Annual Meeting, Boston, 1984. New York, NY, USA, ACM Press, 1984:47-57
33 T.Sellis, Roussopoulos. The R+-tree: a Dynamic Index for Multi-Dimensional Objects. Peter M. Stocker, William Kent. Proceedings of 13th International Conference on Very Large Data Bases, Brighton, England, 1987. San Fransisco, USA, Morgan Kauf- mann, 1987: 507-518
34 N.Beckmann, H.P.Kriegel and R.Schneider. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Hector Garcia-Molina, H. V. Jagadish. Proceedings of the 1990 ACM SIGMOD InternationalConference on Management of Data, Atlantic City, NJ, 1990. New York, NY, USA, ACM Press, 1990: 322-331
35 S. Berchtold. The X-tree: An Index Structure for High-dimensional Data. T. M. Vijayaraman, Alejandro P. Buchmann and C. Mohan. Proceedings of the
22nd VLDB, Mumbai, India, 1996. San Fransisco, USA, Morgan Kaufmann, 1996: 13-37
36 KI Lin and C. Yang. The ANN-Tree: An Index for Efficient Approximate Nearest- Neighbour Search. JH.Son, MH. Kim. Conf. on Database Systems for Advanced App- lications, Hong Kong, China, 2001. Washington, IEEE Computer Society, 2001: 31-38
37 King-Ip Lin, HV Jagadish and Christos Faloutsos. The TV-Tree: An Index Structure for High-dimensional Data. VLDB Journal, 1994, 3(4): 517-542
38 Berchtold S. The IQ-Tree: Independent Quantization for Optimized Query Processing in High-Dimensional Space. Donald Kossmann. Proceedings of the 16th International Conference on Data Engineering, San Diego, CA, 2000. Washington, IEEE Computer Society, 2000: 577-588
39 Y.Cheng, L.H.Cheng, and H.L.Chen. NA-Trees: A Dynamic Index for Spatial Data. Information Science and Engineering, 2003: 103-139
40 S.Shekhar, S.Ravada, and X.Liu. Spatial Databases: Accomplishments and Research Needs. IEEE Trans.Knowledge and Data Eng, 1999, 11(1): 45-55
41 S.Shekhar, M.Coyle. Data Models in Geographic Information Systems. CACN, 1997, 40(4): 104-111
42 Y.I.Chang, B.Y.Yang. Aprime-Number-Based Matrix Strategy for Efficient Iconic Indexing of Symbolic Pictures. Pattern Recognition, 1997, 30(10): 1-13
43 Y. Theodoridis and D. Papadias. Range Queries Involving Spatial Realtions: A performance Analysis. Proceedings of the 2nd Conference on spatiall Information Theory (COSIT), 1995: 176-180
44 C. Freksa. Using Orientation Information for Qualitative Spatial Reasoning. Theories and Methods of Spatio-Temporal Reasoning Geographic Space, 1992, 639: 162-178
45 毛建华,邱小剑,刘丽.空间方向关系推理计算的 NP 完全性研究.江西师范大学学报,2003,27(3):279-282
46 X.Liu, S.Shekhar, S.Chawla. Processing Object-orientation-based Direction Queries. IEEE Transaction of Knowledge and Data Engineering, 15(2), 2003. A summary of results was accepted in ACMGIS 2000
47 X.Liu, S.Shekhar, S.Chawla. Consistency Checking for Euclidean Spatial Constraints: A Dimension Graph Approach, Technical Report TR00-039, Dept. of Compter Sci., U. of Minnesota, A summary of results was accepted in the International Conference of Tools for AI(ICTAI2000)
48 S.Shekhar, X.Liu, S.Chawla. Equivalence Classes of Direction Objects and Applications, Technical Report TR99-027, University of Minnesota, Minneapolis, MN. Will submit to IJGIS
49 曹菡,陈军,杜道生.空间目标方向关系的定性扩展描述.测绘学报, 2001,30(2):162-167
50 闫浩文,郭仁忠.空间方向关系分类研究.测绘工程,2001,10(4):13-15
51 R.Goyal and M.J. Egenhofer. Consistent Queries over Cardinal Directions across Different Levels of Detail.In Proceedings of the 11th International Workshop on Database and Expert Systems Applications, 2000, 2: 1-20
52 S.Prabhakar, Y.Xia, and S.Hambrusch. Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Transaction on Computers, 2002, 51(10): 1124–1140
53 H. Mokhtar, J. Su, and O. H. Ibarra. On Moving Object Queries. Proceedings of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Madison, 2002: 188-198
54 A.Prasad Sistla, O.Wolfson, and S.Chamberlain. Modeling and Querying Moving Objects. ICDE, 1997: 422-432
55 K.Porkaew, I.Lazaridis, and S.Mehrotra. Querying Mobile Objects in Spatio-Temporal Databases. SSTD, 2001: 59-78
56 Y.Tao, D.Papadias. Time-Parameterzied Queries in Spatio-Temporal Databases. SIGMOD Conference, 2002: 334-345
57 Y.Tao, D.Papadias, and Q.Shen. Continuous Nearest Neighbor Search. Proceedings of the 28th VLDB Conference, 2002: 287-298
58 Liu, S.Shekhar, and S.Chawla. Direction Based Query Processing for Mobile Objects. In Proceedings of the Sixth International Symposium on SpatialDatabases, the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems May,Technical Report, TR00-030: 111-132
59 F.Korn and S.Muthukrishnan. Influence Sets Based on Reverse Nearest Neighbor Queries. Weidong Chen, Jeffrey F. Naughton and Philip A. Bernstein. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas,USA,2000. New York, NY, USA, ACM Press, 2000: 201–212
60 C.Yang, K.I.Lin. An Index Structure for Efficient Reverse Nearest Neighbor Queries. George Kollios. Proceedings of the IEEE International Conference on Data Engineering, Heidelberg, Germany, 2001. Washington, IEEE Computer Society, 2001: 4 85-492
61 Renz J, Nebel B. On the complexity of qualitative spatial reasoning. Artificial Intelligence, 1999, 108(1-2): 69~123
62 Renz J. Maximal tractable fragments of the region connection calculus: A complete analysis. In: Dean T, ed. Proc. of the 16th Int'l Conf. on Artificial Intelligence. Stockholm: Morgan Kaufmann, 1999. 448~455
63 Li SJ, Ying MS. Region connection calculus: Its models and composition table. Artificial Intelligence, 2003, 145(1-2): 121~146
64 Bennett B. Spatial reasoning with propositional logic. In: Doyle J, Sandewall E, Torasso P, eds. Proc. of the 4th Int'l Conf. on Knowledge Representation and Reasoning. San Mateo: Morgan Kaufmann, 1994. 51~62
65 Bennett B. Modal logics for qualitative spatial reasoning. Bulletin of the Interest Group in Pure and Applied Logic, 1996, 4(1): 23~45
66 Renz J. A canonical model of the region connection calculus. In: Anthony C, Schubert LK, Shapiro SC, eds. Proc. of the 6th Int'l Conf. on Knowledge Representation and Reasoning. Trento: Morgan Kaufmann, 1998. 330~341
67 Wolter F, Zakharyaschev M. Spatial reasoning in RCC-8 with boolean region terms. In: Werner H, ed. Proc. of the 14th European Conf. on Artificial Intelligence. Berlin: IOS Press, 2000. 244~248
68 Sturm H, Suzuki NY, Wolter F, Zakharyaschev M. Semi-Qualitative reasoning about distances: A preliminary report. In: Ojeda-Aciego M, Guzman I, Brewka G, Pereira LM, eds. Proc. of the European Workshop on Logics in Artificial Intelligence. Malaga: Springer-Verlag, 2000. 37~56
69 Kutz O, Wolter F, Zakharyaschev M. A note on concepts and distances. In: Carole G, McGuinness DL, Ralf M, Patel-Schneider PF, eds. Proc. of the Inte'l Workshop on Description Logic (DL 2001). 113~121
70 Bennett B, Cohn G, Wolter F, Zakharyaschev M. Multi-Dimensional modal logic as a framework for spatio-temporal reasoning. Applied Intelligence, 2002, 3(4): 239~251
71 P.van Beek reasoning about qualitative temporal information. In: Proceedings of AAAI-90. Boston, MA, 1990: 728-734
72 Balbiani, J-F Condotta, and L F del Cerro. A new tractable subclass of the rectangle algebra. IJCAI 1999: 442-447
73 Balbiani, P.Condotta, J.F, and Del Cerro, L. F. A model for reasoning about bidimensional temporal relations. In Proceedings of Principles of Knowledge Representation and Reasoning (KR). Morgan. Kaufmann, Trento, Italy, 1998. 124–130
74 R. Moratz, J. Renz, and D. Wolter, Qualitative Spatial Reasoning about Line Segments, in: Proceedings of the 14th European Conference on Artificial Intelligence (ECAI'00), Berlin, Germany, August 2000: 155-167
75 Spiros Skiadopoulos, Manolis Koubarakis: On the consistency of cardinal direction constraints. Artif. Intell. 163(1): 91-135 (2005)
76 冯玉才,陈琳.空间数据库的方向关系模型.计算机工程与应用,2001,20:115-167
77 闫浩文,郭仁忠.空间方向关系形式化描述模型的研究.测绘学报,2003,32(1):42-46
78 闫浩文,郭仁忠.空间方向关系基础性问题研究.测绘学报,2002,31(4):13-15
79 Clementini, E., Di Felice, P. and Oosterom, P., A small set of formal topological relationships suitable for end-user interatction, D. Abel and B. C. Ooi (eds.) Advances in Spatial Databases:Proc. 3rd Intl. Symposium on Spatial Databases (SSD'93), LNCS No. 692, Spring er-Verlag
80 李成名,陈军.面条模型中空间关系动态推断方法研究.遥感信息,2000(2),14-17
81 陈军,李成名,李志林等.A Voronoi-based 9-intersection Model for spatial relations, Int. J. ofgeograpgical Information Science, 2001, 15(3):201-220
82 Max J, Egenhofer. On the Equivalence of Topological Relations. International Journal of Ge-ographical Information Systems Vol. 8, No. 6, pp. 133-152, 1994
83 Clementini E. and Paolino Di Felice, Topological Invariants for Lines, IEEE Transactions on Knowledge and data Engineering, 1998, 2, Vol. 10(1), 38-54
84 Hekhar and X. Liu. Direction as a Spatial Object. A Summary of Results.The sixth International Symposium on Advances in Geographic Information Systems Washing-Ton, 1998, 1: 69-75
85 Freksa and K. Zimmermann. On the Utilization of Spatial Structures for Cognitively Plausible and Efficient Reasoning. IEEE International Conference on Systems, Man, and Cybernetics, Chicago, IL, 1992, 2: 261-266
86 Zimmermann and C. Freksa. Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge. Applied Intelligence, 1996(6): 49-58
87 Allen. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 1983(26): 823-843
88 C.Freksa. Temporal Reasoning Based on SemiIntervals. Artificial Intelligence, 1992, 54: 199-277
89 Guesgen. Spatial Reasoning Based on Allen’s Temporal Logic. Technical Report, International Computer Science Institute, Berkley, CA. 1989(1): 89-99
90 Mukerjee and G. oe. A Qualitativee Model for Space .EighthNational Conference on Artificial Intelligence, Boston, MA, 1997(2): 721-727
91 Glasgow and D. Papadias. Computational Imagery. Cognitive Science, 1998, 16(3): 355-194
92 GUO Ping, YANG Jun, GAO Yuan, CHEN Haizhu. Presentation and Reasoning of Spatial Objects Direction Relations Based on Strings, International Symposium on IntelligenceComputation & Applications (ISICA 2005), April 2005, pp675-682
93 Nebel B, Burckert H. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. Journal of the Association forComputing Machinery, 1995, 42(1): 42~66
94 Krokhin A, Jeavons P, Jonsson P. A complete classification of complexity in Allen's algebra in the presence of a non-trivial basic relation. In: Nebel B, ed. Proc. of the 17th Int'l Joint Conf. on AI. Seattle: Morgan Kaufmann, 2001. 83~88
95 Renz J. A spatial odyssey of the interval algebra: Directed intervals. In: Nebel B, ed. Proc. of the 17th Int'l Joint Conf. on AI. Seattle: Morgan Kaufmann, 2001. 51~56
96 A. Gerevini & M. Cristani (1997) On finding a solution in temporal constraint satisfaction problems. In: Proceedings of IJCAI-97, Nagoya, Japan. Morgan Kaufmann, Los Altos, CA, pp. 1460–1465
97 M. B. Vilain, Kautz, H. A. & van Beek, P. G. (1989) Constraint propagation algorithms for temporal reasoning: a revised report. In: Readings in Qualitative Reasoning about Physical Systems (D. S. Weld & J. de Kleer, eds). Morgan-Kaufmann, San Mateo, CA, pp. 373–381
98 Wang SS, Liu DY, Yang B. Multi-Dimensional qualitative spatial query language MQS-SQL. Acta Electronica Sinica, 2002, 30(12A):1995~1999 (in Chinese with English abstract)
99 Mackworth, A.K., Consistency in Networks of relations, Artificial Intelligence 8 (1997) 99-118
100 C. Bessiere, A. Isli and G. Ligozat. Global consistency in interval algebra networks: tractable subclasses. Proceedings ECAI’96, Budapest, Hungary, 3-7
101 S.Skiadopoulos and M.Koubarakis. Composing Cardinal Directions Relations. In Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD-01) of LNCS, 2001, (21): 299-317
102 M.Grigni, D.Papadias, C.Papadimitriou. Topological inference, in: Proceedings of IJCAI-95, Montreal, Quebec, 1995: 99-108
103 U.Schmid, F.Wysotzki. Qualitative and Quantitative Approaches to Spatial Inference and the Analysis of Moveents. Technique University Berlin Computer Science Department, 1998, 1: 21-24
104 李成名.空间关系描述的 Voronoi 原理与方法.武汉:测绘出版社,2000:10-13
105 Bessiere, A. Isli and G. Ligozat. Global consistency in interval algebra networks: tractable subclasses. Proceedings ECAI’96, Budapest, Hungary, 1996: 3-7
106 D.Papadias and M.Egenhofer Hierarchical Spatial Reasoning about Direction Relations GeoInformatica 1 (3): 251-273, 1997
107 Lik and A.Klippel. Reasoning about Cardinal Direction Using Grid as Qualitative Geographic Coordinates. Spatial Information Theory-Cognitive and Computational Foundations of Geographic Information Science COSIT’99, Stade,Germany, C.Freksa and D.Mark,Eds.Lecture Notes in Computer Science, 1999(1661): 205-220
108 Matteo Cristani, Reasoning about Qualitative Relations between Straight Lines, Computer Science, Rapporto di ricerca RR 06/2003, 2003: 155-165