semidiscrete: Find Optimal Transport Partition Between pgrid and wpp.

In transport: Computation of Optimal Transport Plans and Wasserstein Distances

Find Optimal Transport Partition Between pgrid and wpp.

Description

Given an object a of class pgrid specifying an image and an object b of class wpp specifiying a more flexible mass distribution at finitely many points, find the partition of the image (and hence the optimal transport map) that minimizes the total transport cost for going from a to b.

Usage

  semidiscrete(a, b, p = 2, method = c("aha"), control = list(), ...)

Arguments

a	an object of class pgrid usually representing an image or the discretization of a measure.
b	an object of class wpp usually having the same total mass as a.
p	the power \geq 1 to which the Euclidean distance between points is taken in order to compute costs. Only p \in \{1,2\} is implemented.
method	the name of the algorithm to use. Currently only aha is supported.
control	a named list of parameters for the chosen method or the result of a call to trcontrol. Currently only the parameters factr and maxit can be set.
...	currently without effect.

Details

This is a wrapper for the functions aha and semidiscrete1. In the former the Aurenhammer–Hoffmann–Aronov (1998) method for p=2 is implemented in the multiscale variant presented in Mérigot (2011). In the latter an adapted Aurenhammer–Hoffmann–Aronov method for p=1 is used that was presented in Hartmann and Schuhmacher (2018).

The present function is automatically called by transport if the first argument is of class pgrid and the second argument is of class wpp.

Value

An object describing the optimal transport partition for a and b.

If p=1 an object of class apollonius_diagram having components sites and weights, as well as (optionally) wasserstein_dist and ret_code (the return code from the call to semidiscrete1).

If p=2 an objectof class power_diagram having components sites and cells, as well as (optionally) wasserstein_dist. sites is here a data.frame with columns xi, eta and w (the weights for the power diagram). cells is a list with as many 2-column matrix components as there are sites, each describing the x- and y-coordinates of the polygonal cell associated with the corresponding site or NULL if the cell of the site is empty.

Plotting methods exist for objects of class apollonius_diagram, power_diagram and for optimal transport maps represented by either of the two.

Note

For p=1 this function requires the Computational Geometry Algorithms Library (CGAL), available at https://www.cgal.org. Adapt the file src/Makevars according to the instructions given there and re-install from source.

Internally the code from liblbfgs 1.10 by Naoaki Okazaki (2010) is used.

Author(s)

Dominic Schuhmacher [e-mail]
Björn Bähre [e-mail]
Valentin Hartmann [e-mail]

References

F. Aurenhammer, F. Hoffmann and B. Aronov (1998). Minkowski-type theorems and least-squares clustering. Algorithmica 20(1), 61–76.

V. Hartmann and D. Schuhmacher (2017). Semi-discrete optimal transport — the case p=1. Preprint arXiv:1706.07650

M. Karavelas and M. Yvinec. 2D Apollonius Graphs (Delaunay Graphs of Disks). In CGAL User and Reference Manual. CGAL Editorial Board, 4.12 edition, 2018

Q. Mérigot (2011). A multiscale approach to optimal transport. Computer Graphics Forum 30(5), 1583–1592. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1111/j.1467-8659.2011.02032.x")}

Naoaki Okazaki (2010). libLBFGS: a library of Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS). Version 1.10

See Also

plot, transport, aha, semidiscrete1

Examples

##  See examples for function transport

transport documentation built on Sept. 17, 2024, 1:08 a.m.