Sparse geometric graphs with small dilation
- 作者：Boris Aronov ; Mark de Berg ; Otfried Cheong ; Joachim Gudmundsson ; Herman Haverkort ; Michiel Smid ; Antoine Vigneron
- 关键词：Dilation ; Spanner ; Geometric network ; Small-dilation spanning tree
- 刊名：Computational Geometry
- 出版年：2008
- 期刊代码：18_09257721
- 类别：cp
- 出版时间：August 2008
- 卷：40
- 期：3
- 页码：207-219
- 文件大小：273 K
摘要
Given a set S of n points in 
, and an integer k such that 0
k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.
k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.