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

Computer, Electrical and Mathematical Sciences and Engineering

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 - Dec 1 2005
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

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

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

year = "2005",

month = dec,

day = "1",

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

note = "16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

}

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

PY - 2005/12/1

Y1 - 2005/12/1

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

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this