www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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
URI: http://hdl.handle.net/1942/23452
DOI: 10.1016/j.jcss.2016.12.001
ISI #: 000395957600009
ISSN: 0022-0000
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Peer-reviewed author version858.43 kBAdobe PDF
Published version564.26 kBAdobe PDF

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