Geometric spanner

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner.^[1]

In computational geometry, the concept was first discussed by L.P. Chew in 1986,^[2] although the term "spanner" was not used in the original paper.

The notion of graph spanners has been known in graph theory: t-spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric.

Spanners may be used in computational geometry for solving some proximity problems. They have also found applications in other areas, such as in motion planning, in telecommunication networks: network reliability, optimization of roaming in mobile networks, etc.

Different spanners and quality measures

There are different measures which can be used to analyze the quality of a spanner. The most common measures are edge count, total weight and maximum vertex degree. Asymptotically optimal values for these measures are $O(n)$ edges, $O(MST)$ weight and $O(1)$ maximum degree (here MST denotes the weight of the minimum spanning tree).

Finding a spanner in the Euclidean plane with minimal dilation over n points with at most m edges is known to be NP-hard.^[3]

Many spanner algorithms exist which excel in different quality measures. Fast algorithms include the WSPD spanner and the Theta graph which both construct spanners with a linear number of edges in $O(n\log n)$ time. If better weight and vertex degree is required the Greedy spanner can be computed in near quadratic time.

The Theta graph

The Theta graph or $\Theta$ -graph belongs to the family of cone-based spanners. The basic method of construction involves partitioning the space around each vertex into a set of cones, which themselves partition the remaining vertices of the graph. Like Yao Graphs, a $\Theta$ -graph contains at most one edge per cone; where they differ is how that edge is selected. Whereas Yao Graphs will select the nearest vertex according to the metric space of the graph, the $\Theta$ -graph defines a fixed ray contained within each cone (conventionally the bisector of the cone) and selects the nearest neighbour with respect to orthogonal projections to that ray.

See the page on the Theta graph for more detailed information on this spanner.

The greedy spanner

The greedy spanner or greedy graph is defined as the graph resulting from repeatedly adding an edge between the closest pair of points without a t-path. Algorithms which compute this graph are referred to as greedy spanner algorithms. From the construction it trivially follows that the greedy graph is a t-spanner.

The greedy spanner was first discovered in 1989 independently by Althöfer^[4] and Bern (unpublished).

The greedy spanner achieves asymptotically optimal edge count, total weight and maximum vertex degree and also performs best on these measures in practice.

Computing the greedy spanner

The original naive algorithm for computing the greedy spanner sorts all pairs of points in ascending order by distance from each other. Starting at the closest pair of points it repeatedly checks if there is a t-path connecting the pair by computing the shortest path. If no t-path exists it adds an edge for this pair. Since there are a quadratic number of pairs of points and computing the shortest path on a sparse graph can be done in $O(n\log n)$ time using Dijkstra's algorithm the naive algorithm computes the greedy spanner in $O(n^3 \log n)$ time. Since the naive algorithm sorts a quadratic number of edges its space usage is $O(n^{2})$ .

Several faster, near-quadratic time, algorithms exist. Most of these algorithms rely on some kind of caching or other method of reusing information gained from shortest path queries.

The asymptotically fastest greedy spanner algorithm runs in $O(n^2 \log n)$ time using $O(n^{2})$ space.^[5]

The quadratic space usage of this algorithm makes using it to compute the greedy graph on large point sets impossible in practice. A Linear space algorithm exists which runs in $O(n^2 \log^2 n)$ time^[6] making it possible to compute the greedy graph on larger point sets.

The Delaunay triangulation

Chew's main result was that for a set of points in the plane there is a triangulation of this pointset such that for any two points there is a path along the edges of the triangulation with length at most $\scriptstyle\sqrt 10$ the Euclidean distance between the two points. The result was applied in motion planning for finding reasonable approximations of shortest paths among obstacles.

The best upper bound known for the Euclidean Delaunay triangulation is that it is a $\scriptstyle{(4\sqrt{3}/9)\pi} \approx 2.418$ -spanner for its vertices.^[7] The lower bound has been increased from $\scriptstyle{{\pi}/2}$ to just over that, to 1.5846. ^[8]

The Well-separated pair decomposition (WSPD) spanner

The spanner based on the WSPD is constructed the following way. Construct the graph with the point set $S$ as vertex set and for each pair $\{A,B\}$ in a WSPD, add an edge from an arbitrary point $a\in A$ to an arbitrary point $b\in B$ . Note that the resulting graph has a linear number of edges because a WSPD has a linear number of pairs.^[9]

Proof of correctness of the algorithm ^[10]
We need these two properties of the WSPD: Lemma 1: Let $\{A,B\}$ be a well-separated pair with respect to $s$ . Let $p, p' \in A$ and $q \in B$ . Then, $\|pp'\| \leq (2/s)\|pq\|$ . Lemma 2: Let $\{A,B\}$ be a well-separated pair with respect to $s$ . Let $p, p' \in A$ and $q, q' \in B$ . Then, $\|p'q'\| \leq (1+ 4/s)\|pq\|$ . Let $\{A,B\}$ be a well-separated pair with respect to $s$ in a WSPD. Let $[a,b]$ be the edge connecting $A$ to $B$ . Let any point $p\in A$ and $q \in B$ . Because of the definition of the WSPD, it is only necessary to prove that there is a $t$ -spanner path, or $t$ -path for short, between $p$ and $q$ noted $P_{pq}$ . Let the length of the path $P_{pq}$ be noted $\|P_{pq}\|$ . Suppose there is a $t$ -path between any pair of points which distance is less than or equal to $\|pq\|$ and that $s > 2$ . From the triangle inequality, the assumptions and the fact that $\|pa\|\leq (2/s)\|pq\|\Rightarrow \|pa\|<\|pq\|$ and $\|bq\|\leq (2/s)\|pq\|\Rightarrow \|bq\|<\|pq\|$ according to Lemma 1, we have: $\|P_{pq}\|\leq t\|pa\|+\|ab\|+t\|bq\|$ From Lemma 1 and 2, we obtain: ${\begin{aligned}\|P_{pq}\|&\leq t(2/s)\|pq\|+(1+4/s)\|pq\|+t(2/s)\|pq\|\\&=t(4/s)\|pq\|+(1+4/s)\|pq\|\\&=\left({\frac {4t+4}{s}}\right)\|pq\|+\|pq\|\\&=\left({\frac {4(t+1)}{s}}+1\right)\|pq\|\end{aligned}}$ So what we want is: ${\begin{aligned}t&={\frac {4(t+1)}{s}}+1\\t-1&={\frac {4(t+1)}{s}}\\s(t-1)&=4(t+1)\\s(t-1)-4(t+1)&=0\\st-s-4t-4&=0\\t(s-4)-s-4&=0\\t(s-4)&=s+4\\t&={\frac {s+4}{s-4}}\end{aligned}}$ So, if $t=(s+4)/(s-4)$ and $s>4$ , then we have a $t$ -spanner for the point set $S$ .

Proof of correctness of the algorithm ^[10]

We need these two properties of the WSPD:

Lemma 1: Let $\{A,B\}$ be a well-separated pair with respect to $s$ . Let $p, p' \in A$ and $q \in B$ . Then, $|pp'| \leq (2/s)|pq|$ .

Lemma 2: Let $\{A,B\}$ be a well-separated pair with respect to $s$ . Let $p, p' \in A$ and $q, q' \in B$ . Then, $|p'q'| \leq (1+ 4/s)|pq|$ .

Let $\{A,B\}$ be a well-separated pair with respect to $s$ in a WSPD. Let $[a,b]$ be the edge connecting $A$ to $B$ . Let any point $p\in A$ and $q \in B$ . Because of the definition of the WSPD, it is only necessary to prove that there is a $t$ -spanner path, or $t$ -path for short, between $p$ and $q$ noted $P_{pq}$ . Let the length of the path $P_{pq}$ be noted $|P_{pq}|$ .

Suppose there is a $t$ -path between any pair of points which distance is less than or equal to $|pq|$ and that $s > 2$ . From the triangle inequality, the assumptions and the fact that $|pa|\leq (2/s)|pq|\Rightarrow |pa|<|pq|$ and $|bq|\leq (2/s)|pq|\Rightarrow |bq|<|pq|$ according to Lemma 1, we have:

$|P_{pq}|\leq t|pa|+|ab|+t|bq|$

From Lemma 1 and 2, we obtain:

${\begin{aligned}|P_{pq}|&\leq t(2/s)|pq|+(1+4/s)|pq|+t(2/s)|pq|\\&=t(4/s)|pq|+(1+4/s)|pq|\\&=\left({\frac {4t+4}{s}}\right)|pq|+|pq|\\&=\left({\frac {4(t+1)}{s}}+1\right)|pq|\end{aligned}}$

So what we want is:

${\begin{aligned}t&={\frac {4(t+1)}{s}}+1\\t-1&={\frac {4(t+1)}{s}}\\s(t-1)&=4(t+1)\\s(t-1)-4(t+1)&=0\\st-s-4t-4&=0\\t(s-4)-s-4&=0\\t(s-4)&=s+4\\t&={\frac {s+4}{s-4}}\end{aligned}}$

So, if $t=(s+4)/(s-4)$ and $s>4$ , then we have a $t$ -spanner for the point set $S$ .

According to the proof, it is then possible to have an arbitrary value for $t$ by isolating $s$ from $t=(s+4)/(s-4)$ which gives $s=4(t+1)/(t-1)$ .

References

↑ Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks, Cambridge University Press, ISBN 0-521-81513-4 .
↑ Chew, L. Paul (1986), "There is a planar graph almost as good as the complete graph", Proc. 2nd Annual Symposium on Computational Geometry, pp. 169–177, doi:10.1145/10515.10534 .
↑ Klein, Rolf; Kutz, Martin (2007), "Computing Geometric Minimum-Dilation Graphs is NP-Hard", in Kaufmann, Michael; Wagner, Dorothea, Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Germany, 2006, Lecture Notes in Computer Science, 4372, Springer Verlag, pp. 196–207, doi:10.1007/978-3-540-70904-6, ISBN 978-3-540-70903-9 .
↑ I. Althöfer; G. Das; D. P. Dobkin; D. Joseph; J. Soares. (1993). "On sparse spanners of weighted graphs.". Discrete & Computational Geometry. 9: 81–100. doi:10.1007/bf02189308.
↑ P. Bose, P. Carmi, M. Farshi, A. Maheshwari, and M. Smid. (2010). "Computing the greedy spanner in near-quadratic time.". Algorithmica. 58: 711–729. doi:10.1007/s00453-009-9293-4.
↑ S. P. A. Alewijnse, Q. W. Bouts, A. P. T. Brink and K. Buchin. (2013). "Computing the Greedy Spanner in Linear Space", Proc. 21st Annual European Symposium on Algorithms, Sophia Antipolis, France, 2013, Lecture Notes in Computer Science 8125, Springer Verlag, pp. 37-48
↑ Keil, J. M.; Gutwin, C. A. (1992), "Classes of graphs which approximate the complete Euclidean graph", Discrete and Computational Geometry, 7 (1): 13–28, doi:10.1007/BF02187821 .
↑ Bose, P.; Devroye, L.; Loeffler, M.; Snoeyink, J.; Verma, V. (2009), "The spanning ratio of the Delaunay triangulation is greater than $\scriptstyle {\pi /2}$ ", Proc. 21st Canadian Conf. Computational Geometry, Vancouver, pp. 165–167 .
↑ Callahan, P. B.; Kosaraju, S. R. (January 1995). "A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields". Journal of the ACM. 42 (1): 67–90. doi:10.1145/200836.200853.
↑ Callahan, Paul B.; Kosaraju, S. Rao (1993). "Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions". Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '93. Austin, Texas, USA: Society for Industrial and Applied Mathematics. pp. 291–300. doi:10.1145/313559.313777. ISBN 0-89871-313-7.

This article is issued from Wikipedia - version of the 5/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.