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.