Distribution-sensitive construction of the greedy spanner (extended abstract)

S.P.A. Alewijnse, Q.W. Bouts, A.P. Brink, ten, K. Buchin

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

34 Downloads (Pure)

Samenvatting

The greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it take O(n^2) time, limiting its applicability on large data sets. We observe that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly, and few or no ‘long’ edges that can usually be determined quickly using local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets. This characterization gives a O(n log^2 n log^2 log n) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points.
Originele taal-2Engels
Titel30th European Workshop on Computational Geometry (EuroCG 2014, Ein-Gedi, Israel, March 3-5, 2014)
Pagina's1-4
StatusGepubliceerd - 2014
Evenement30th European Workshop on Computational Geometry (EuroCG 2014) - Dead Sea, Israël
Duur: 3 mrt 20145 mrt 2014
Congresnummer: 30
https://www.cs.bgu.ac.il/~eurocg14/

Workshop

Workshop30th European Workshop on Computational Geometry (EuroCG 2014)
Verkorte titelEuroCG 2014
LandIsraël
StadDead Sea
Periode3/03/145/03/14
Ander30th European Workshop on Computational Geometry
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Distribution-sensitive construction of the greedy spanner (extended abstract)'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Alewijnse, S. P. A., Bouts, Q. W., Brink, ten, A. P., & Buchin, K. (2014). Distribution-sensitive construction of the greedy spanner (extended abstract). In 30th European Workshop on Computational Geometry (EuroCG 2014, Ein-Gedi, Israel, March 3-5, 2014) (blz. 1-4)