Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/23452
Title: | On the realisability of double-cross matrices by polylines in the plane | Authors: | KUIJPERS, Bart MOELANS, Bart |
Issue Date: | 2017 | Source: | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 86, p. 117-135 | 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. | Notes: | Kuijpers, B (reprint author), UHasselt Hasselt Univ, Agoralaan,Gebouw D, B-3590 Diepenbeek, Belgium. bart.kuijpers@uhasselt.be; bart.moelans@unleashed.be | Keywords: | Spatial reasoning; Double-cross calculus; Qualitative description of polylines; Computational algebraic geometry; Algorithmic complexity | Document URI: | http://hdl.handle.net/1942/23452 | ISSN: | 0022-0000 | e-ISSN: | 1090-2724 | DOI: | 10.1016/j.jcss.2016.12.001 | ISI #: | 000395957600009 | Rights: | Copyright is with Journal of Computer and System Sciences (Elsevier). | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2018 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2016-JCSS-Kuijpers-Moelans-Final.pdf | Peer-reviewed author version | 586.59 kB | Adobe PDF | View/Open |
Kuijpers2017.pdf Restricted Access | Published version | 564.26 kB | Adobe PDF | View/Open Request a copy |
Page view(s)
60
checked on Sep 7, 2022
Download(s)
98
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.