Distribution-sensitive construction of the greedy spanner

DOI10.1007/978-3-662-44777-2_6MaRDI QIDQ2921394zbMATH OpenOpenAlexFDO

Authors Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.1085, https://research.tue.nl/nl/publications/distributionsensitive-construction-of-the-greedy-spanner(8fe96391-23cc-445b-b36f-cd5351085cea).html

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 Omega(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: we give a geometric property that holds with high probability on such point sets. This property implies that if an edge set on these points has t-paths between pairs of points `close' to each other, then it has t-paths between all pairs of points. 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. We also use this characterization to give a O((n + |E|) log^2 n log log n) expected time algorithm on uniformly distributed points that determines if E is a t-spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E.

Recommendations

• Distribution-sensitive construction of the greedy spanner
• Computing the greedy spanner in linear space
• Computing the greedy spanner in linear space
• A framework for computing the greedy spanner
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners

Cited in

(13)

• Computing the greedy spanner in near-quadratic time
• Geometric spanner games
• \(\delta\)-greedy \(t\)-spanner
• On path-greedy geometric spanners
• Computing the greedy spanner in linear space
• New Doubling Spanners: Better and Simpler
• Visualization of geometric spanner algorithms
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• The emergence of sparse spanners and greedy well-separated pair decomposition
• A framework for computing the greedy spanner
• Distribution-sensitive construction of the greedy spanner
• Algorithms – ESA 2005
• Computing the greedy spanner in linear space

This page was built for publication: Distribution-sensitive construction of the greedy spanner

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921394)