drezner: Run an Improved Version of the Algorithm by Drezner, Mehrez...

In ttbary: Barycenter Methods for Spatial Point Patterns

Run an Improved Version of the Algorithm by Drezner, Mehrez and Wesolowsky for Finding Barycenters Based on Limited Distances

Description

Find a barycenter of a 2-d point cloud based on minimizing the p-th power of the Euclidean distance, cut off at C=2*\code{penalty}^p. In addition to using a pre-screening procedure to further alleviate the computational burden of the original algorithm, an option may be specified to allow the algorithm to return NA if no location in 2-d space is "good enough".

Usage

drezner(clusterx, clustery, penalty, p = 2, reduction = TRUE, aleph = FALSE)

Arguments

clusterx, clustery	vectors of x- and y-coordinates for the point cloud.
penalty	the p-th power of the Euclidean distance is cut off at 2*\code{penalty}^p. To cut off at C, set \code{penalty} = (C/2)^{1/p}.
p	the exponent for the distances and cutoffs. Currently only implemented for p=2.
reduction	logical. Shall the pre-screening procedure be applied?
aleph	logical. Shall the returned value be NA if no good barycenter can be found?

Details

For points z_1,...,z_n with x-coordinates clusterx and y-coordinates clustery find a minimizer b* (barycenter) of

γ(b) = ∑_{i=1}^n \min{\|z_i-b\|^p, C}

or return NA if γ(b) > (n/2)*C for all b in R^2.

The original algorithm is due to Drezner, Mehrez and Wesolowsky (1991). The improvements are from Müller, Schöbel and Schuhmacher (2022).

Value

A list containing the following components:

barycenterx,barycentery	the x- and y-coordinates of the barycenter b* that was found. May both be NA if option aleph=TRUE and no actual barycenter is good enough.
cost	the total cost gamma(b^*) of the barycenter .
calculations	If reduction=FALSE, the number of point pairs from which the barycenter candidates are calculated. Each point pair yields eight candidates.
skipped	If reduction=TRUE, the number of skipped point pairs due to the pre-screening procedure.

Author(s)

Raoul Müller [e-mail]

References

Zvi Drezner, Avram Mehrez and George O. Wesolowsky (1991).
The facility location problem with limited distances.
Transportation Science 25.3 (1991): 183-187.
www.jstor.org/stable/25768490

Raoul Müller, Anita Schöbel and Dominic Schuhmacher (2022).
Location problems with cutoff.
Preprint arXiv:2203.00910

Examples

  x <- rnorm(20)
  y <- rnorm(20)
  plot(x, y, asp=1)
  res <- drezner(x, y, 2)
  points(res$barycenterx, res$barycentery, col=2)
  res <- drezner(x, y, 0.5)
  points(res$barycenterx, res$barycentery, col=4)

ttbary documentation built on Nov. 16, 2022, 5:15 p.m.