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".
drezner(clusterx, clustery, penalty, p = 2, reduction = TRUE, aleph = FALSE)A list containing the following components:
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.
the total cost \(\gamma(b^*)\) of the barycenter .
If reduction=FALSE, the number of point pairs from which the barycenter candidates are calculated.
Each point pair yields eight candidates.
If reduction=TRUE, the number of skipped point pairs
due to the pre-screening procedure.
vectors of x- and y-coordinates for the point cloud.
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}\).
the exponent for the distances and cutoffs. Currently only implemented for p=2.
logical. Shall the pre-screening procedure be applied?
logical. Shall the returned value be NA if no good barycenter can be found?
Raoul Müller raoul.mueller@uni-goettingen.de
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).
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
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)
Run the code above in your browser using DataLab