TY - GEN

T1 - Fast pruning of geometric spanners

AU - Gudmundsson, J.

AU - Narasimhan, G.

AU - Smid, M.H.M.

PY - 2005

Y1 - 2005

N2 - Let S be a set of points in R d . Given a geometric spanner graph, G = (S,E), with constant stretch factor t, and a positive constant e, we show how to construct a (1+e)-spanner of G with O(|S|) edges in time O(|E|+|S|log|S|) . Previous algorithms require a preliminary step in which the edges are sorted in non-decreasing order of their lengths and, thus, have running time O(|E| log |S|). We obtain our result by designing a new algorithm that finds the pair in a well-separated pair decomposition separating two given query points. Previously, it was known how to answer such a query in O(log|S|) time. We show how a sequence of such queries can be answered in O(1) amortized time per query, provided all query pairs are from a polynomially bounded range.

AB - Let S be a set of points in R d . Given a geometric spanner graph, G = (S,E), with constant stretch factor t, and a positive constant e, we show how to construct a (1+e)-spanner of G with O(|S|) edges in time O(|E|+|S|log|S|) . Previous algorithms require a preliminary step in which the edges are sorted in non-decreasing order of their lengths and, thus, have running time O(|E| log |S|). We obtain our result by designing a new algorithm that finds the pair in a well-separated pair decomposition separating two given query points. Previously, it was known how to answer such a query in O(log|S|) time. We show how a sequence of such queries can be answered in O(1) amortized time per query, provided all query pairs are from a polynomially bounded range.

U2 - 10.1007/978-3-540-31856-9_42

DO - 10.1007/978-3-540-31856-9_42

M3 - Conference contribution

SN - 3-540-24998-2

T3 - Lecture Notes in Computer Science

SP - 508

EP - 520

BT - STACS 2005 (Proceedings 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005)

A2 - Diekert, V.

A2 - Durand, B.

PB - Springer

CY - Berlin

ER -