On the realisability of double-cross matrices by polylines in the plane
| Autor: | Bart Kuijpers, Bart Moelans |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Computer Networks and Communications
Plane (geometry) Applied Mathematics 010102 general mathematics Spatial intelligence 010103 numerical & computational mathematics Decision problem Computer Science::Computational Geometry 01 natural sciences Spatial reasoning Double-cross calculus Qualitative description of polylines Computational algebraic geometry Algorithmic complexity Theoretical Computer Science Decidability Combinatorics Matrix (mathematics) Line segment Computational Theory and Mathematics Position (vector) 0101 mathematics Mathematics |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|