Greedy geometric spanner

Last updated
Greedy geometric spanner of 100 random points with stretch factor t = 2 Greedy geometric spanner 2.svg
Greedy geometric spanner of 100 random points with stretch factor t = 2
Greedy geometric spanner of the same points with stretch factor t = 1.1 Greedy geometric spanner 1.1.svg
Greedy geometric spanner of the same points with stretch factor t = 1.1

In computational geometry, a greedy geometric spanner is an undirected graph whose distances approximate the Euclidean distances among a finite set of points in a Euclidean space. The vertices of the graph represent these points. The edges of the spanner are selected by a greedy algorithm 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 [1] and conference paper [2] and subsequent journal paper by Ingo Althöfer et al. [3] These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.

Contents

Greedy geometric spanners have bounded degree, a linear total number of edges, and total weight close to that of the Euclidean minimum spanning tree. Although known construction methods for them are slow, fast approximation algorithms with similar properties are known. [4]

Construction

The greedy geometric spanner is determined from an input consisting a set of points and a parameter . The goal is to construct a graph whose shortest path distances are at most times the geometric distances between pairs of points. It may be constructed by a greedy algorithm that adds edges one at a time to the graph, starting from an edgeless graph with the points as its vertices. All pairs of points are considered, in sorted (ascending) order by their distances, starting with the closest pair. For each pair of points, the algorithm tests whether the graph constructed so far already contains a path from to with length at most . If not, the edge with length is added to the graph. By construction, the resulting graph is a geometric spanner with stretch factor at most . [3]

A naive implementation of this method would take time on inputs with points. This is because the considerations for each of the pairs of points involve an instance of Dijkstra's algorithm to find a shortest path in a graph with edges. It uses space to store the sorted list of pairs of points. More careful algorithms can construct the same graph in time , [5] or in space . [6] A construction for a variant of the greedy spanner that uses graph clustering to quickly approximate the graph distances runs in time in Euclidean spaces of any bounded dimension, and can produce spanners with (approximately) the same properties as the greedy spanners. [7] [8] The same method can be extended to spaces with bounded doubling dimension. [4]

Properties

The same greedy construction produces spanners in arbitrary metric spaces, but in Euclidean spaces it has good properties some of which do not hold more generally. [4]

The greedy geometric spanner in any metric space always contains the minimum spanning tree of its input, because the greedy construction algorithm follows the same insertion order of edges as Kruskal's algorithm 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 is large enough (e.g. , where is the number of vertices in the graph) the two algorithms produce the same output. [3]

In Euclidean spaces of bounded dimension, for any constant , the greedy geometric -spanners on sets of points have bounded degree, implying that they also have edges. [9] [10] [7] This property does not extend even to well-behaved metric spaces: there exist spaces with bounded doubling dimension where the greedy spanner has unbounded vertex degree. [4] [11] [12] However, in such spaces the number of edges is still . [4]

Greedy geometric spanners in bounded-dimension Euclidean spaces also have total weight at most a constant times the total weight of the Euclidean minimum spanning tree. [9] [10] [7] This property remains true in spaces of bounded doubling dimension. [4]

Related Research Articles

<span class="mw-page-title-main">Dual polyhedron</span> Polyhedron associated with another by swapping vertices for faces

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

<span class="mw-page-title-main">Delaunay triangulation</span> Triangulation method named after Boris Delaunay

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry an arrangement of lines is the subdivision of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

<span class="mw-page-title-main">Euclidean minimum spanning tree</span> Shortest network connecting points

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. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

<span class="mw-page-title-main">No-three-in-line problem</span> Geometry problem on grid points

The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. This number is at most , because points in a grid would include a row of three or more points, by the pigeonhole principle. The problem was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".

In computational geometry, the Theta graph, or -graph, is a type of geometric spanner similar to a Yao graph. 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 -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 -graph defines a fixed ray contained within each cone and selects the nearest neighbor with respect to orthogonal projections to that ray. The resulting graph exhibits several good spanner properties.

<span class="mw-page-title-main">Unit disk graph</span> Intersection graph of unit disks in the plane

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are subgraphs of unit distance graphs.

In geometry, the Beckman–Quarles theorem, named after Frank S. Beckman and Donald A. Quarles Jr., states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. Beckman and Quarles published this result in 1953; it was later rediscovered by other authors, and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.

<span class="mw-page-title-main">K-set (geometry)</span> Points separated from others by a line

In discrete geometry, a -set of a finite point set in the Euclidean plane is a subset of elements of that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a -set of a finite point set is a subset of elements that can be separated from the remaining points by a hyperplane. In particular, when , the line or hyperplane that separates a -set from the rest of is a halving line or halving plane.

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.

<span class="mw-page-title-main">Yao graph</span> Undirected graph with graph distances linearly bounded w.r.t. Euclidean distances

In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance.

<span class="mw-page-title-main">Widest path problem</span> Path-finding using high-weight graph edges

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In distributed computing and geometric graph theory, greedy embedding is a process of assigning coordinates to the nodes of a telecommunications network in order to allow greedy geographic routing to be used to route messages within the network. Although greedy embedding has been proposed for use in wireless sensor networks, in which the nodes already have positions in physical space, these existing positions may differ from the positions given to them by greedy embedding, which may in some cases be points in a virtual space of a higher dimension, or in a non-Euclidean geometry. In this sense, greedy embedding may be viewed as a form of graph drawing, in which an abstract graph is embedded into a geometric space.

<span class="mw-page-title-main">Flip graph</span> A graph that encodes local operations in mathematics

In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.

The stretch factor of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space S is embedded into another metric space T by a metric map, a continuous one-to-one function f that preserves or reduces the distance between every pair of points. Then the embedding gives rise to two different notions of distance between pairs of points in S. Any pair of points (x,y) in S has both an intrinsic distance, the distance from x to y in S, and a smaller extrinsic distance, the distance from f(x) to f(y) in T. The stretch factor of the pair is the ratio between these two distances, d(f ,f )/d(x,y). The stretch factor of the whole mapping is the supremum of the stretch factors of all pairs of points. The stretch factor has also been called the distortion or dilation of the mapping.

Deborah A. Joseph is an American computer scientist known for her research in computational geometry, computational biology, and computational complexity theory. She is a professor emeritus of computer science at the University of Wisconsin–Madison.

<span class="mw-page-title-main">Gautam Das (computer scientist)</span> Indian computer scientist

Gautam Das is a computer scientist in the field of databases research. He is an ACM Fellow and IEEE Fellow.

References

  1. Das, Gautam (1990), Approximation Schemes in Computational Geometry (doctoral dissertation), University of Wisconsin, MR   2685391, OCLC   22935858
  2. Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah (1990), "Generating sparse spanners for weighted graphs", SWAT 90, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 26–37, doi:10.1007/3-540-52846-6_75, ISBN   978-3-540-52846-3 , retrieved 2021-03-16
  3. 1 2 3 Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José (1993), "On sparse spanners of weighted graphs", Discrete & Computational Geometry , 9 (1): 81–100, doi: 10.1007/BF02189308 , MR   1184695
  4. 1 2 3 4 5 6 Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv: 1605.06852 , doi:10.1145/2933057.2933114
  5. Bose, Prosenjit; Carmi, Paz; Farshi, Mohammad; Maheshwari, Anil; Smid, Michiel (2010), "Computing the greedy spanner in near-quadratic time", Algorithmica , 58 (3): 711–729, doi:10.1007/s00453-009-9293-4, MR   2672477
  6. Alewijnse, Sander P. A.; Bouts, Quirijn W.; ten Brink, Alex P.; Buchin, Kevin (2015), "Computing the greedy spanner in linear space", Algorithmica , 73 (3): 589–606, arXiv: 1306.4919 , doi:10.1007/s00453-015-0001-2, MR   3411749
  7. 1 2 3 Das, Gautam; Narasimhan, Giri (1997), "A fast algorithm for constructing sparse Euclidean spanners", International Journal of Computational Geometry and Applications , 7 (4): 297–315, doi:10.1142/S0218195997000193, MR   1460840
  8. Gudmundsson, Joachim; Levcopoulos, Christos; Narasimhan, Giri (2002), "Fast greedy algorithms for constructing sparse geometric spanners", SIAM Journal on Computing , 31 (5): 1479–1500, doi:10.1137/S0097539700382947, MR   1936655
  9. 1 2 Chandra, Barun; Das, Gautam; Narasimhan, Giri; Soares, José (1995), "New sparseness results on graph spanners", International Journal of Computational Geometry and Applications , 5 (1–2): 125–144, doi:10.1142/S0218195995000088, MR   1331179
  10. 1 2 Das, Gautam; Heffernan, Paul; Narasimhan, Giri (1993), "Optimally sparse spanners in 3-dimensional Euclidean space", Proceedings of the Ninth Annual Symposium on Computational Geometry (SoCG '93), New York, NY, USA: ACM, pp. 53–62, doi:10.1145/160985.160998
  11. Har-Peled, Sariel; Mendel, Manor (2006), "Fast construction of nets in low-dimensional metrics and their applications", SIAM Journal on Computing , 35 (5): 1148–1184, doi:10.1137/S0097539704446281, MR   2217141
  12. Smid, Michiel H. M. (2009), "The weak gap property in metric spaces of bounded doubling dimension", in Albers, Susanne; Alt, Helmut; Näher, Stefan (eds.), Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 5760, Springer, pp. 275–289, doi:10.1007/978-3-642-03456-5_19