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. This decision problem concerns the description of polylines in the plane by means of their double-cross matrix. In such a matrix, the relative position of each pair of line segments in a polyline is expressed by means of a 4-tuple over {−, 0, +}. However, not any such matrix of 4-tuples is the double-cross matrix of a polyline. This gives rise to the decision problem: given a matrix of such 4-tuples, decide whether it is the double-cross matrix of a polyline. This problem is decidable, but it is NP-hard. In this paper, we give polynomial- time algorithms for the cases where consecutive line segments in a polyline make angles that are multiples of 90 or 45 and for the case where, apart from an input matrix, the successive angles of a polyline are also given as input.