Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/23452
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | KUIJPERS, Bart | - |
dc.contributor.author | MOELANS, Bart | - |
dc.date.accessioned | 2017-04-06T14:51:15Z | - |
dc.date.available | 2017-04-06T14:51:15Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 86, p. 117-135 | - |
dc.identifier.issn | 0022-0000 | - |
dc.identifier.uri | http://hdl.handle.net/1942/23452 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.rights | Copyright is with Journal of Computer and System Sciences (Elsevier). | - |
dc.subject.other | Spatial reasoning; Double-cross calculus; Qualitative description of polylines; Computational algebraic geometry; Algorithmic complexity | - |
dc.title | On the realisability of double-cross matrices by polylines in the plane | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 135 | - |
dc.identifier.spage | 117 | - |
dc.identifier.volume | 86 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Kuijpers, B (reprint author), UHasselt Hasselt Univ, Agoralaan,Gebouw D, B-3590 Diepenbeek, Belgium. bart.kuijpers@uhasselt.be; bart.moelans@unleashed.be | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.1016/j.jcss.2016.12.001 | - |
dc.identifier.isi | 000395957600009 | - |
item.contributor | KUIJPERS, Bart | - |
item.contributor | MOELANS, Bart | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2018 | - |
item.fullcitation | KUIJPERS, Bart & MOELANS, Bart (2017) On the realisability of double-cross matrices by polylines in the plane. In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 86, p. 117-135. | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 0022-0000 | - |
crisitem.journal.eissn | 1090-2724 | - |
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.