Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414805 | Computational Geometry | 2008 | 18 Pages |
Abstract
In a geometric network G=(S,E), the graph distance between two vertices u,v∈S 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 δ>1, it is NP-hard to determine whether a spanning tree of S with dilation at most δ exists.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics