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 | Keywords: | spatial reasoning; double-cross calculus; qualitative description of polylines; computational algebraic geometry; algorithmic complexity | Document URI: | http://hdl.handle.net/1942/21222 | Category: | R2 | Type: | Research Report |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2015-KM-DCM-real.pdf | 668.95 kB | Adobe PDF | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.