In computational geometry, a greedy geometric spanner is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

whose distances approximate the

Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore o ...

s among a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. ...

of points in a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean sp ...

. The vertices of the graph represent these points. The edges of the spanner are selected by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locall ...

that includes an edge whenever its two endpoints are not connected by a short path of shorter edges. The greedy spanner was first described in the PhD thesis of

Gautam Das Gautam Das ( – November 17, 2005) was a Bangladeshi print journalist and bureau chief for '' Dainik Samakal'' in Faridpur, Dhaka Division, Bangladesh when he was murdered in his office. He was known for his reporting on crime and corrupt ...

and conference paper and subsequent journal paper by

Ingo Althöfer Ingo Althöfer (born 1961) is a German mathematician at the University of Jena, where he holds the chair of operations research. Althöfer earned his PhD in 1986 at Bielefeld University. His dissertation, ''Asymptotic Properties of Certain Comp ...

et al. These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction. Greedy geometric spanners have bounded

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...

, a linear total number of edges, and total weight close to that of the

Euclidean minimum spanning tree A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. ...

. Although known construction methods for them are slow, fast

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

s with similar properties are known.

Construction

The greedy geometric spanner is determined from an input consisting a set of points and a parameter

t\ge 1

. The goal is to construct a graph whose shortest path distances are at most

t

times the geometric distances between pairs of points. It may be constructed by a

that adds edges one at a time to the graph, starting from an

edgeless graph In the mathematical field of graph theory, the term "null graph" may refer either to the order- zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is ...

with the points as its vertices. All pairs of points are considered, in sorted (ascending) order by their distances, starting with the

closest pair The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean ...

. For each pair

(u,v)

of points, the algorithm tests whether the graph constructed so far already contains a path from

u

v

with length at most

t\cdot d(u,v)

. If not, the edge

uv

with length

d(u,v)

is added to the graph. By construction, the resulting graph is a

geometric spanner A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path ...

with

stretch factor The stretch factor (i.e., bilipschitz constant) of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space is embedded into another metric space by a metric map, a continuous one-to-one funct ...

at most

t

. A naive implementation of this method would take time

O(n^3\log n)

on inputs with

n

points. This is because the considerations for each of the

O(n^2)

pairs of points involve an instance of

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...

to find a shortest path in a graph with

O(n)

edges. It uses

O(n^2)

space to store the sorted list of pairs of points. More careful algorithms can construct the same graph in time

O(n^2\log n)

, or in space

O(n)

. A construction for a variant of the greedy spanner that uses graph clustering to quickly approximate the graph distances runs in time

O(n\log n)

in Euclidean spaces of any bounded dimension, and can produce spanners with (approximately) the same properties as the greedy spanners. The same method can be extended to spaces with bounded

doubling dimension In mathematics, a metric space with metric is said to be doubling if there is some doubling constant such that for any and , it is possible to cover the ball with the union of at most balls of radius . The base-2 logarithm of is called the ...

Properties

The same greedy construction produces spanners in arbitrary

metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...

s, but in Euclidean spaces it has good properties some of which do not hold more generally. The greedy geometric spanner in any metric space always contains the

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

of its input, because the greedy construction algorithm follows the same insertion order of edges as

Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that ...

for minimum spanning trees. If the greedy spanner algorithm and Kruskal's algorithm are run in parallel, considering the same pairs of vertices in the same order, each edge added by Kruskal's algorithm will also be added by the greedy spanner algorithm, because the endpoints of the edge will not already be connected by a path. In the limiting case when

t

is large enough (e.g.

t>n

, where

n

is the number of vertices in the graph) the two algorithms produce the same output. In Euclidean spaces of bounded dimension, for any constant

t

, the greedy geometric

t

-spanners on sets of

n

points have bounded

, implying that they also have

O(n)

edges. This property does not extend even to well-behaved metric spaces: there exist spaces with bounded

where the greedy spanner has unbounded vertex degree. However, in such spaces the number of edges is still

O(n)

. Greedy geometric spanners in bounded-dimension Euclidean spaces also have total weight at most a constant times the total weight of the

. This property remains true in spaces of bounded doubling dimension.

References

{{reflist, refs= {{Citation , last1 = Althöfer , first1 = Ingo , author1-link = Ingo Althöfer , last2 = Das , first2 = Gautam , author2-link = Gautam_Das_(computer_scientist) , last3 = Dobkin , first3 = David , author3-link = David P. Dobkin , last4 = Joseph , first4 = Deborah , author4-link = Deborah Joseph , title=Generating sparse spanners for weighted graphs , date=1990 , url=http://dx.doi.org/10.1007/3-540-52846-6_75 , work=SWAT 90 , pages=26–37 , place=Berlin, Heidelberg , publisher=Springer Berlin Heidelberg , doi = 10.1007/3-540-52846-6_75 , isbn=978-3-540-52846-3 , access-date=2021-03-16 {{citation , last1 = Das , first1 = Gautam , author1-link = Gautam_Das_(computer_scientist) , url = http://worldcat.org/oclc/22935858 , mr = 2685391 , publisher = University of Wisconsin , title = Approximation Schemes in Computational Geometry , type = doctoral dissertation , oclc=22935858 , year = 1990 {{citation , last1 = Alewijnse , first1 = Sander P. A. , last2 = Bouts , first2 = Quirijn W. , last3 = ten Brink , first3 = Alex P. , last4 = Buchin , first4 = Kevin , doi = 10.1007/s00453-015-0001-2 , issue = 3 , journal =

Algorithmica ''Algorithmica'' is a monthly peer-reviewed scientific journal focusing on research and the application of computer science algorithms. The journal was established in 1986 and is published by Springer Science+Business Media. The editor in chief is ...

, mr = 3411749 , pages = 589–606 , title = Computing the greedy spanner in linear space , volume = 73 , year = 2015, arxiv = 1306.4919 {{citation , last1 = Althöfer , first1 = Ingo , author1-link = Ingo Althöfer , last2 = Das , first2 = Gautam , author2-link = Gautam_Das_(computer_scientist) , last3 = Dobkin , first3 = David , author3-link = David P. Dobkin , last4 = Joseph , first4 = Deborah , author4-link = Deborah Joseph , last5 = Soares , first5 = José , doi = 10.1007/BF02189308 , issue = 1 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ge ...

, mr = 1184695 , pages = 81–100 , title = On sparse spanners of weighted graphs , volume = 9 , year = 1993, doi-access = free {{citation , last1 = Bose , first1 = Prosenjit , author1-link = Jit Bose , last2 = Carmi , first2 = Paz , last3 = Farshi , first3 = Mohammad , last4 = Maheshwari , first4 = Anil , last5 = Smid , first5 = Michiel , doi = 10.1007/s00453-009-9293-4 , issue = 3 , journal =

, mr = 2672477 , pages = 711–729 , title = Computing the greedy spanner in near-quadratic time , volume = 58 , year = 2010 {{citation , last1 = Chandra , first1 = Barun , last2 = Das , first2 = Gautam , author2-link = Gautam_Das_(computer_scientist) , last3 = Narasimhan , first3 = Giri , last4 = Soares , first4 = José , doi = 10.1142/S0218195995000088 , issue = 1–2 , journal =

International Journal of Computational Geometry and Applications The ''International Journal of Computational Geometry and Applications'' (IJCGA) is a bimonthly journal published since 1991, by World Scientific. It covers the application of computational geometry in design and analysis of algorithms, focusing o ...

, mr = 1331179 , pages = 125–144 , title = New sparseness results on graph spanners , volume = 5 , year = 1995 {{citation , last1 = Das , first1 = Gautam , author1-link = Gautam_Das_(computer_scientist) , last2 = Heffernan , first2 = Paul , last3 = Narasimhan , first3 = Giri , contribution = Optimally sparse spanners in 3-dimensional Euclidean space , doi = 10.1145/160985.160998 , location = New York, NY, USA , pages = 53–62 , publisher = ACM , title = Proceedings of the Ninth Annual

Symposium on Computational Geometry The International Symposium on Computational Geometry (SoCG) is an academic conference in computational geometry. It was founded in 1985, and was originally sponsored by the SIGACT and SIGGRAPH Special Interest Groups of the Association for Compu ...

(SoCG '93) , year = 1993, doi-access = free {{citation , last1 = Das , first1 = Gautam , author1-link = Gautam_Das_(computer_scientist) , last2 = Narasimhan , first2 = Giri , doi = 10.1142/S0218195997000193 , issue = 4 , journal =

, mr = 1460840 , pages = 297–315 , title = A fast algorithm for constructing sparse Euclidean spanners , volume = 7 , year = 1997 {{citation , last1 = Filtser , first1 = Arnold , last2 = Solomon , first2 = Shay , contribution = The greedy spanner is existentially optimal , doi = 10.1145/2933057.2933114 , location = New York, NY, USA , pages = 9–17 , publisher = ACM , title = Proceedings of the 2016 ACM

Symposium on Principles of Distributed Computing The Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery (special interest groups SIGACT and SIGOPS). Scope and re ...

(PODC '16), year = 2016 , arxiv = 1605.06852 {{citation , last1 = Gudmundsson , first1 = Joachim , last2 = Levcopoulos , first2 = Christos , last3 = Narasimhan , first3 = Giri , doi = 10.1137/S0097539700382947 , issue = 5 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...

, mr = 1936655 , pages = 1479–1500 , title = Fast greedy algorithms for constructing sparse geometric spanners , volume = 31 , year = 2002 {{citation , last1 = Har-Peled , first1 = Sariel , author1-link = Sariel Har-Peled , last2 = Mendel , first2 = Manor , doi = 10.1137/S0097539704446281 , issue = 5 , journal =

, mr = 2217141 , pages = 1148–1184 , title = Fast construction of nets in low-dimensional metrics and their applications , volume = 35 , year = 2006 {{citation , last = Smid , first = Michiel H. M. , editor1-last = Albers , editor1-first = Susanne , editor1-link = Susanne Albers , editor2-last = Alt , editor2-first = Helmut , editor2-link = Helmut Alt , editor3-last = Näher , editor3-first = Stefan , contribution = The weak gap property in metric spaces of bounded doubling dimension , doi = 10.1007/978-3-642-03456-5_19 , pages = 275–289 , publisher = Springer , series = Lecture Notes in Computer Science , title = Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday , volume = 5760 , year = 2009 Geometric algorithms Geometric graphs