Sparse geometric graphs with small dilation

Boris Aronov, Mark De Berg, Otfried Cheong*, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, Antoine Vigneron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

Given a set S of n points in RD, 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.

Original languageEnglish (US)
Pages (from-to)207-219
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume40
Issue number3
DOIs
StatePublished - Aug 2008
Externally publishedYes

Keywords

  • Dilation
  • Geometric network
  • Small-dilation spanning tree
  • Spanner

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Sparse geometric graphs with small dilation'. Together they form a unique fingerprint.

Cite this