Sparse geometric graphs with small dilation

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

doi:10.1016/j.comgeo.2007.07.004

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 journal › Article › peer-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 language	English (US)
Pages (from-to)	207-219
Number of pages	13
Journal	Computational Geometry: Theory and Applications
Volume	40
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2007.07.004
State	Published - Aug 2008
Externally published	Yes

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

Access to Document

10.1016/j.comgeo.2007.07.004

Cite this

@article{94a786dc6f8845178f489120ca64e95f,

title = "Sparse geometric graphs with small dilation",

abstract = "Given a set S of n points in RD, and an integer k such that 0≤k",

keywords = "Dilation, Geometric network, Small-dilation spanning tree, Spanner",

author = "Boris Aronov and {De Berg}, Mark and Otfried Cheong and Joachim Gudmundsson and Herman Haverkort and Michiel Smid and Antoine Vigneron",

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{\textquoteright} 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{\textquoteright}s Backing Australia{\textquoteright}s Ability initiative, in part through the Australian Research Council.",

year = "2008",

month = aug,

doi = "10.1016/j.comgeo.2007.07.004",

language = "English (US)",

volume = "40",

pages = "207--219",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Sparse geometric graphs with small dilation

AU - Aronov, Boris

AU - De Berg, Mark

AU - Cheong, Otfried

AU - Gudmundsson, Joachim

AU - Haverkort, Herman

AU - Smid, Michiel

AU - Vigneron, Antoine

N1 - 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.

PY - 2008/8

Y1 - 2008/8

N2 - Given a set S of n points in RD, and an integer k such that 0≤k

AB - Given a set S of n points in RD, and an integer k such that 0≤k

KW - Dilation

KW - Geometric network

KW - Small-dilation spanning tree

KW - Spanner

UR - http://www.scopus.com/inward/record.url?scp=84867961523&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2007.07.004

DO - 10.1016/j.comgeo.2007.07.004

M3 - Article

AN - SCOPUS:84867961523

SN - 0925-7721

VL - 40

SP - 207

EP - 219

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -

Sparse geometric graphs with small dilation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this