lazyGreedy: Applying the Lazy-Greedy Algorithm

In lazygreedy: Applying the Lazy-Greedy Spanning Algorithm

Description

Function lazyGreedy is an R wrapper for an efficient C++ implementation of the Lazy-Greedy spanning algorithm. The C++ implementation executes many thousands of times faster than a pure R implementation. Both the algorithm and (most of) the C++ implementation were developed by Quirijn W. Bouts, Alex P. ten Brink, and Kevin Buchin.

Usage

lazyGreedy(V, t)

Arguments

V	a numeric n-by-2 matrix the ith row of which contains the location in R^2 of vertex i.
t	the desired dilation, a positive real number.

Value

Function lazyGreedy returns a greedy t-spanner for the set of vertices V. The result takes the form of an edge list.

References

Bouts, Q. W., ten Brink, A. P., and Buchin, K. (2014). A framework for computing the greedy spanner. In 30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014) (pp. 11-19). Association for Computing Machinery, Inc.

Examples

n = 20
V = cbind(runif(n), runif(n))
spanner = lazyGreedy(V, t = 2)

## Not run: 
require("network")
G = network(spanner, directed = FALSE)
plot(G, coord = V, label = 1:n, jitter = FALSE)

## End(Not run)

lazygreedy documentation built on Jan. 13, 2021, 6:53 a.m.