Sparse geometric graphs with small dilation

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

doi:10.1007/11602613_7

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 proceeding › Conference contribution › peer-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 language	English (US)
Title of host publication	Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Pages	50-59
Number of pages	10
DOIs	https://doi.org/10.1007/11602613_7
State	Published - 2005
Externally published	Yes
Event	16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China Duration: Dec 19 2005 → Dec 21 2005

Publication series

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

Other

Other	16th International Symposium on Algorithms and Computation, ISAAC 2005
Country/Territory	China
City	Hainan
Period	12/19/05 → 12/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: [email protected] (M. de Berg), [email protected] (O. Cheong), [email protected] (J. Gudmundsson), [email protected] (H. Haverkort), [email protected] (M. Smid), [email protected] (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

Access to Document

10.1007/11602613_7

Cite this

Aronov, B., De Berg, M., Cheong, O., Gudmundsson, J., Haverkort, H., & Vigneron, A. (2005). Sparse geometric graphs with small dilation. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings (pp. 50-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS). https://doi.org/10.1007/11602613_7

@inproceedings{a4eea979bea749089ee0303d626111c8,

title = "Sparse geometric graphs with small dilation",

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.",

author = "Boris Aronov and {De Berg}, Mark and Otfried Cheong and Joachim Gudmundsson and Herman Haverkort 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: [email protected] (M. de Berg), [email protected] (O. Cheong), [email protected] (J. Gudmundsson), [email protected] (H. Haverkort), [email protected] (M. Smid), [email protected] (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.; 16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

year = "2005",

doi = "10.1007/11602613_7",

language = "English (US)",

isbn = "3540309357",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "50--59",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

}

Aronov, B, De Berg, M, Cheong, O, Gudmundsson, J, Haverkort, H & Vigneron, A 2005, Sparse geometric graphs with small dilation. in Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3827 LNCS, pp. 50-59, 16th International Symposium on Algorithms and Computation, ISAAC 2005, Hainan, China, 12/19/05. https://doi.org/10.1007/11602613_7

Sparse geometric graphs with small dilation. / Aronov, Boris; De Berg, Mark; Cheong, Otfried et al.
Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. 2005. p. 50-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Sparse geometric graphs with small dilation

AU - Aronov, Boris

AU - De Berg, Mark

AU - Cheong, Otfried

AU - Gudmundsson, Joachim

AU - Haverkort, Herman

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: [email protected] (M. de Berg), [email protected] (O. Cheong), [email protected] (J. Gudmundsson), [email protected] (H. Haverkort), [email protected] (M. Smid), [email protected] (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 - 2005

Y1 - 2005

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

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

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

U2 - 10.1007/11602613_7

DO - 10.1007/11602613_7

M3 - Conference contribution

AN - SCOPUS:33744953548

SN - 3540309357

SN - 9783540309352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 50

EP - 59

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -

Aronov B, De Berg M, Cheong O, Gudmundsson J, Haverkort H, Vigneron A. Sparse geometric graphs with small dilation. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. 2005. p. 50-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11602613_7

Sparse geometric graphs with small dilation

Abstract

Publication series

Other

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this