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/dataset: | 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 | Size | Format | |
---|---|---|---|---|
fp30.pdf | Published version | 397.96 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.