Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951179 | Journal of Computer and System Sciences | 2017 | 19 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bart Kuijpers, Bart Moelans,