Approximating the Earth Mover’s Distance between sets of points and line segments

Marc van Kreveld; Frank Staals; Amir Vaxman; Jordi L. Vermeulen

Approximating the Earth Mover’s Distance between sets of points and line segments

Marc van Kreveld, Frank Staals, Amir Vaxman, Jordi L. Vermeulen

Research output: Contribution to conference › Paper › peer-review

Abstract / Description of output

We show that a (1 + ε)-approximation algorithm exists for the Earth Mover’s Distance between a set of n points and set of n line segments with equal total weight.

Original language	English
Number of pages	6
Publication status	Published - 20 Mar 2019
Event	The 35th European Workshop on Computational Geometry 2019 - Utrecht, Netherlands Duration: 18 Mar 2019 → 20 Mar 2019 Conference number: 35 http://www.eurocg2019.uu.nl/home

Workshop

Workshop	The 35th European Workshop on Computational Geometry 2019
Abbreviated title	EuroCG 2019
Country/Territory	Netherlands
City	Utrecht
Period	18/03/19 → 20/03/19
Internet address	http://www.eurocg2019.uu.nl/home

Access to Document

http://www.eurocg2019.uu.nl/papers/24.pdfLicence: All Rights Reserved

Cite this

@conference{75b1de91afd64af9a880217b4238d57f,

title = "Approximating the Earth Mover{\textquoteright}s Distance between sets of points and line segments",

abstract = "We show that a (1 + ε)-approximation algorithm exists for the Earth Mover{\textquoteright}s Distance between a set of n points and set of n line segments with equal total weight.",

author = "{van Kreveld}, Marc and Frank Staals and Amir Vaxman and Vermeulen, {Jordi L.}",

year = "2019",

month = mar,

day = "20",

language = "English",

note = "The 35th European Workshop on Computational Geometry 2019, EuroCG 2019 ; Conference date: 18-03-2019 Through 20-03-2019",

url = "http://www.eurocg2019.uu.nl/home",

}

TY - CONF

T1 - Approximating the Earth Mover’s Distance between sets of points and line segments

AU - van Kreveld, Marc

AU - Staals, Frank

AU - Vaxman, Amir

AU - Vermeulen, Jordi L.

N1 - Conference code: 35

PY - 2019/3/20

Y1 - 2019/3/20

N2 - We show that a (1 + ε)-approximation algorithm exists for the Earth Mover’s Distance between a set of n points and set of n line segments with equal total weight.

AB - We show that a (1 + ε)-approximation algorithm exists for the Earth Mover’s Distance between a set of n points and set of n line segments with equal total weight.

M3 - Paper

T2 - The 35th European Workshop on Computational Geometry 2019

Y2 - 18 March 2019 through 20 March 2019

ER -

Approximating the Earth Mover’s Distance between sets of points and line segments

Abstract / Description of output

Workshop

Access to Document

Fingerprint

Cite this