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. (c) 2007 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2008-08
Language
ENG
Keywords

MINIMUM SPANNING-TREES; POINT SETS; SPANNERS; NETWORKS

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.40, no.3, pp.207 - 219

ISSN
0925-7721
DOI
10.1016/j.comgeo.2007.07.004
URI
http://hdl.handle.net/10203/7709
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
v18otfried.pdf(291.29 kB)Download
  • Hit : 1089
  • Download : 580
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 15 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0