skip to main content
10.1145/1463434.1463475acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
research-article

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

Published: 05 November 2008 Publication History

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]
K. D. Forbus. Qualitative physics: Past, present, and future. In Readings in Qualitative Reasoning about Physical Systems, pages 11--39. Kaufmann, 1990.
[10]
C. Freksa. Using orientation information for qualitative spatial reasoning. In A. F. et al., editor, Spatio-Temporal Reasoning, volume 639 of Lecture Notes in Computer Science, pages 162--178. Springer, 1992.
[11]
F. Giannotti and D. Pedreschi, editors. Mobility, Data Mining and Privacy - Geographic Knowledge Discovery. Springer, 2008.
[12]
R. H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005.
[13]
B. Kuijpers, B. Moelans, and N. V. de Weghe. Qualitative polyline similarity testing with applications to query-by-sketch, indexing and classification. In Proceedings ACM-GIS '06, pages 11--18, 2006.
[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]
G. Trajcevski, H. Ding, P. Scheuermann, R. Tamassia, and D. Vaccaro. Dynamics-aware similarity of moving objects trajectories. In Proceedings ACM-GIS'07, pages 75--82, 2007.
[16]
M. J. van Kreveld and J. Luo. The definition and computation of trajectory and subtrajectory similarity. In Proceedings ACM-GIS, 2007.
[17]
M. Vlachos, M. Hadjieleftheriou, D. Gunopulos, and E. J. Keogh. Indexing multi-dimensional time-series with support for multiple distance measures. In Proceedings ACM SIGKDD, pages 216--225, 2003.
[18]
O. Wolfson. Moving objects information management: The database challenge. In Proceedings of NGITS, pages 75--89, 2002.
[19]
K. Zimmermann and C. Freksa. Qualitative spatial reasoning using orientation, distance, and path knowledge. Appl. Intell., 6(1):49--58, 1996.

Cited By

View all
  • (2016)Algebraic and Geometric Characterizations of Double-Cross Matrices of PolylinesISPRS International Journal of Geo-Information10.3390/ijgi50901525:9(152)Online publication date: 27-Aug-2016

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems
      November 2008
      559 pages
      ISBN:9781605583235
      DOI:10.1145/1463434
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 05 November 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. double-cross calculus
      2. polylines
      3. similarity

      Qualifiers

      • Research-article

      Funding Sources

      Conference

      GIS '08
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 257 of 1,238 submissions, 21%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)2
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 13 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2016)Algebraic and Geometric Characterizations of Double-Cross Matrices of PolylinesISPRS International Journal of Geo-Information10.3390/ijgi50901525:9(152)Online publication date: 27-Aug-2016

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media