Sparse geometric graphs with small dilation
<|reference_start|>Sparse geometric graphs with small dilation: Given a set S of n points in R^D, 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(n log n). For any k, we also construct planar n-point sets for which any geometric graph with n-1+k edges has dilation Omega(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.<|reference_end|>
@article{aronov2007sparse,
    title={Sparse geometric graphs with small dilation},
    author={Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson,
  Herman Haverkort, Michiel Smid, Antoine Vigneron},
    journal={arXiv preprint arXiv:cs/0702080},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0702080},
    primaryClass={cs.CG}
}