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

29 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

Bibliographical note

Funding Information:
✩ B.A. was supported in part by NSF ITR Grant CCR-00-81964 and by a grant from the US–Israel Binational Science Foundation. Part of the work was carried out while B.A. was visiting TU/e in February 2004 and in the summer of 2005. O.C. was supported by LG Electronics. M.d.B. was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. M.S. was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). A.V. was supported by NUS research grant R-252-000-166-112. * Corresponding author. E-mail addresses: mdberg@win.tue.nl (M. de Berg), otfried@tclab.kaist.ac.kr (O. Cheong), joachim.gudmundsson@nicta.com.au (J. Gudmundsson), cs.herman@haverkort.net (H. Haverkort), michiel@scs.carleton.ca (M. Smid), antoine.vigneron@jouy.inra.fr (A. Vigneron). URL: http://cis.poly.edu/~aronov (B. Aronov). 1 NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.

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