1. ScholarBank@NUS
  2. 1. Staff
  3. Staff Publications
Please use this identifier to cite or link to this item: https://doi.org/10.1007/11602613_7
DC FieldValue
dc.titleSparse geometric graphs with small dilation
dc.contributor.authorAronov, B.
dc.contributor.authorDe Berg, M.
dc.contributor.authorCheong, O.
dc.contributor.authorGudmundsson, J.
dc.contributor.authorHaverkort, H.
dc.contributor.authorVigneron, A.
dc.date.accessioned2013-07-04T08:29:03Z
dc.date.available2013-07-04T08:29:03Z
dc.date.issued2005
dc.identifier.citationAronov, B.,De Berg, M.,Cheong, O.,Gudmundsson, J.,Haverkort, H.,Vigneron, A. (2005). Sparse geometric graphs with small dilation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3827 LNCS : 50-59. ScholarBank@NUS Repository. <a href="https://doi.org/10.1007/11602613_7" target="_blank">https://doi.org/10.1007/11602613_7</a>
dc.identifier.isbn3540309357
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/41503
dc.description.abstractGiven a set S of n points in the plane, and an integer k such that 0 ≤ k &lt; 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. © Springer-Verlag Berlin Heidelberg 2005.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/11602613_7
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1007/11602613_7
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume3827 LNCS
dc.description.page50-59
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.