Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Space-Efficient Approximation Scheme for Circular Earth Mover Distance
verfasst von : Joshua Brody, Hongyu Liang, Xiaoming Sun
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Earth Mover Distance (EMD) between point sets
A
and
B
is the minimum cost of a bipartite matching between
A
and
B
. EMD is an important measure for estimating similarities between objects with quantifiable features and has important applications in several areas including computer vision. The streaming complexity of approximating EMD between point sets in a two-dimensional discretized grid is an important open problem proposed in [8,9].
We study the problem of approximating EMD in the streaming model, when points lie on a discretized circle. Computing the EMD in this setting has applications to computer vision [13] and can be seen as a special case of computing EMD on a discretized grid. We achieve a (1 ±
ε
) approximation for EMD in
$\tilde O(\varepsilon^{-3})$
space, for every 0 <
ε
< 1. To our knowledge, this is the first streaming algorithm for a natural and widely applied EMD model that matches the space bound asked in [9].