Computing a minimum-dilation spanning tree is NP-hard

O. Cheong, H.J. Haverkort, M. Lee

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)188-205
JournalComputational Geometry
Issue number3
Publication statusPublished - 2008


Dive into the research topics of 'Computing a minimum-dilation spanning tree is NP-hard'. Together they form a unique fingerprint.

Cite this