Abstract
Given a set of n points (known as terminals) and a set of λ ≥ 2 uniformly distributed (legal) orientations in the plane, the uniform orientation Steiner tree problem asks for a minimum-length network that interconnects the terminals with the restriction that the network is composed of line segments using legal orientations only. This problem is also known as the λ-geometry Steiner tree problem. We show that for any fixed λ > 2 the uniform orientation Steiner tree problem is NP-hard. In fact we prove a strictly stronger result, namely that the problem is NP-hard even when the terminals are restricted to lying on two parallel lines.
| Original language | English |
|---|---|
| Journal | International Journal of Computational Geometry and Applications |
| Volume | 24 |
| Issue number | 2 |
| ISSN | 0218-1959 |
| Publication status | Published - 2014 |
| Externally published | Yes |
Keywords
- Steiner tree problem
- λ-geometry
- fixed orientation metric
- computational complexity
- NP-hard