On the realisability of double-cross matrices by polylines in the plane

Abstract

We study a decision problem that emerges from the area of spatial reasoning, but that is also of interest to the area of computational algebraic geometry. This decision problem concerns the use of constraint calculi in qualitative spatial reasoning. One such qualitative calculus describes polylines in the plane by means of their double-cross matrix. In such a matrix, the rela- tive position (or orientation) of each pairs of line segments of a polyline is expresses by means of a 4-tuple, whose entries come from the set {−, 0, +}. However, not any N × N matrix of 4-tuples from {−, 0, +} is the double-cross matrix of a polyline with N line segments. This gives rise to the following decision problem : given an N × N matrix of 4-tuples from {−, 0, +}, decide whether it is the double-cross matrix of a polyline with N line segments, and if it is, given an example of a polyline that realises the matrix. It is known that this problem is decidable, but it is NP-hard and the best, known algorithms have exponential time complexity. In this paper, we give polynomial time algorithms for the case where the attention is restricted to polylines in which consecutive line segments make angles that are multiples of 90◦ or 45◦, respectively. For the more complicated case of 45◦-polylines, we also introduce the polar-coordinate representation of double-cross matrices.