Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/21222

Title: On the realisability of double-cross matrices by polylines in the plane
Authors: Kuijpers, Bart
Moelans, Bart
Issue Date: 2015
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.
Notes: Preprint submitted to Journal of Computer and System Sciences
URI: http://hdl.handle.net/1942/21222
Category: R2
Type: Research Report
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A668.95 kBAdobe PDF

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