drezner {ttbary}

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 \cdot \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,\ldots,z_n with x-coordinates clusterx and y-coordinates clustery find a minimizer b^* (barycenter) of

\gamma(b) = \sum_{i=1}^n \min\{\|z_i-b\|^p, C\}

or return NA if \gamma(b) > \frac{n}{2}C for all b \in \mathbf{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)