Document Server@UHasselt >
Research >
Research publications >

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
Issue Date: 2008
Publisher: ACM New York, NY, USA
Citation: 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.
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:

Description SizeFormat
Published version397.96 kBAdobe PDF

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