TY - JOUR

T1 - Computing a minimum-dilation spanning tree is NP-hard

AU - Cheong, O.

AU - Haverkort, H.J.

AU - Lee, M.

PY - 2008

Y1 - 2008

N2 - In a geometric network G=(S,E), the graph distance between two vertices u,vS is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation d>1, it is NP-hard to determine whether a spanning tree of S with dilation at most d exists.

AB - In a geometric network G=(S,E), the graph distance between two vertices u,vS is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation d>1, it is NP-hard to determine whether a spanning tree of S with dilation at most d exists.

U2 - 10.1016/j.comgeo.2007.12.001

DO - 10.1016/j.comgeo.2007.12.001

M3 - Article

SN - 0925-7721

VL - 41

SP - 188

EP - 205

JO - Computational Geometry

JF - Computational Geometry

IS - 3

ER -