Sparse geometric graphs with small dilation

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

Given a set S of n points in the plane, 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, and dilation O(n/(k + 1)) can be computed in time O(n log n). We also construct 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)
Title of host publicationAlgorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Pages50-59
Number of pages10
DOIs
StatePublished - 2005
Externally publishedYes
Event16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China
Duration: Dec 19 2005Dec 21 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3827 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Symposium on Algorithms and Computation, ISAAC 2005
Country/TerritoryChina
CityHainan
Period12/19/0512/21/05

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.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this