lazygreedy (version 1.0)

lazyGreedy: Applying the Lazy-Greedy 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 \(i\)th 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

# NOT RUN {
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)
# }