The uniform orientation Steiner tree problem is NP-hard

TY - JOUR

T1 - The uniform orientation Steiner tree problem is NP-hard

AU - Brazil, Marcus

AU - Zachariasen, Martin

PY - 2014/6/16

Y1 - 2014/6/16

N2 - 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.

AB - 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.

U2 - 10.1142/S0218195914500046

DO - 10.1142/S0218195914500046

M3 - Journal article

SN - 0218-1959

VL - 24

SP - 87

EP - 105

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 2

ER -