Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/8990
Title: Towards a geometric interpretation of double-cross matrix-based similarity of polylines
Authors: KUIJPERS, Bart 
MOELANS, Bart 
Issue Date: 2008
Publisher: ACM New York, NY, USA
Source: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems. p. 280-287.
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.
Keywords: double-cross calculus, polylines, similarity
Document URI: http://hdl.handle.net/1942/8990
Link to publication: http://doi.acm.org/10.1145/1463434.1463475
ISBN: 978-1-60558-323-5
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
fp30.pdfPublished version397.96 kBAdobe PDFView/Open
Show full item record

Page view(s)

46
checked on May 17, 2022

Download(s)

140
checked on May 17, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.