Towards a geometric interpretation of double-cross matrix-based similarity of polylines

ABSTRACT

One of the formalisms to qualitatively describe polylines in the plane are double-cross matrices. In a double-cross matrix the relative position of any two line segments in a polyline is described with respect to a double cross based on their start points. Two polylines are called DC-similar if their double-cross matrices are identical. Although double-cross matrices have been widely applied, a geometric interpretation of the similarity they express is still lacking. In this paper, we provide a first step in the geometric interpretation of this qualitative definition of similarity. In particular, we give an effective characterization of what DC-similarity means for polylines that are drawn on a grid. We also provide algorithms that, given a DC-matrix, check whether it is realizable by a polyline on a grid and that construct, if possible, in quadratic time example polylines that satisfy this matrix. We also describe algorithms to reconstruct polylines, satisfying a given double-cross matrix, in the two-dimensional plane, that is, not necessarily on a grid.

REFERENCES

• 1: Mathematica 6. http://www.wolfram.com.
• 2: Qepcad. http://www.cs.usna.edu/~qepcad.
• 3: Redlog. http://www.fmi.uni-passau.de/~redlog.
• 4: B. Caviness and J. Johnson, editors. Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer, 1998.
• 5: A. G. Cohn and J. Renz. Qualitative spatial representation and reasoning. In Handbook of Knowledge Representation, chapter 13, pages 551--596. Elsevier, 2007.
• 6: N. V. de Weghe. Representing and Reasoning about Moving Objects: A Qualitative Approach. PhD thesis, Ghent University, Faculty of Sciences, Department of Geography, 2004.
• 7: N. V. de Weghe, B. Kuijpers, P. Bogaert, and P. D. Maeyer. A qualitative trajectory calculus and the composition of its relations. In GeoS, volume 3799 of Lecture Notes in Computer Science, pages 60--76. Springer, 2005.
• 8: M. J. Egenhofer and D. M. Mark. Naive geography. In COSIT, pages 1--15, 1995.
• 9: Kenneth D. Forbus, Qualitative physics: past present and future, Readings in qualitative reasoning about physical systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 10: 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
• 11: Fosca Giannotti , Dino Pedreschi, Mobility, Data Mining and Privacy: Geographic Knowledge Discovery, Springer Publishing Company, Incorporated, 2008
• 12: R. H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005.
• 13: Bart Kuijpers , Bart Moelans , Nico Van de Weghe, Qualitative polyline similarity testing with applications to query-by-sketch, indexing and classification, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183475]
• 14: M. Nanni, B. Kuijpers, C. Körner, M. May, and D. Pedreschi. Spatiotemporal data mining. In Mobility, Data Mining and Privacy, chapter 10, pages 267--296. Springer, 2008.
• 15: Goce Trajcevski , Hui Ding , Peter Scheuermann , Roberto Tamassia , Dennis Vaccaro, Dynamics-aware similarity of moving objects trajectories, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington [doi>10.1145/1341012.1341027]
• 16: Marc van Kreveld , Jun Luo, The definition and computation of trajectory and subtrajectory similarity, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington [doi>10.1145/1341012.1341068]
• 17: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956777]
• 18: Ouri Wolfson, Moving Objects Information Management: The Database Challenge, Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems, p.75-89, June 24-25, 2002
• 19: K. Zimmermann and C. Freksa. Qualitative spatial reasoning using orientation, distance, and path knowledge. Appl. Intell., 6(1):49--58, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Theory

Keywords:
double-cross calculus, polylines, similarity