Middle curves based on discrete Frechet distance

被引：4

作者：

Ahn, Hee-Kap ^{[1
]}

Alt, Helmut ^{[2
]}

Buchin, Maike ^{[3
]}

Oh, Eunjin ^{[4
]}

Scharf, Ludmila ^{[2
]}

Wenk, Carola ^{[5
]}

机构：

[1] Pohang Univ Sci & Technol, Pohang, South Korea

[2] Free Univ Berlin, Berlin, Germany

[3] Ruhr Univ Bochum, Bochum, Germany

[4] POSTECH, Dept Comp Sci & Engn, Pohang, South Korea

[5] Tulane Univ, New Orleans, LA 70118 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2020年 / 89卷

基金：

美国国家科学基金会;

关键词：

Representative Curve; Frechet distance; Exact Algorithms;

D O I：

10.1016/j.comgeo.2020.101621

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given a set of polygonal curves, we present algorithms for computing a middle curve that serves as a representative for the entire set of curves. We require that the middle curve consists of vertices of the input curves and that it minimizes the maximum discrete Frechet distance to all input curves. We consider three different variants of a middle curve depending on in which order vertices of the input curves may occur on the middle curve, and provide algorithms for computing each variant. (C) 2020 Elsevier B.V. All rights reserved.

引用

页数：15

共 10 条

[1] COMPUTING THE FRECHET DISTANCE BETWEEN 2 POLYGONAL CURVES
ALT, H
GODAU, M
[J]. INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (1-2) : 75 - 91
[2] Buchin K., 2016, EUROCG
[3] Median Trajectories
Buchin, Kevin
Buchin, Maike
van Kreveld, Marc
Loffler, Maarten
Silveira, Rodrigo I.
Wenk, Carola
Wiratma, Lionov
[J]. ALGORITHMICA, 2013, 66 (03) : 595 - 614
[4] DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES
Buchin, Kevin
Buchin, Maike
Gudmundsson, Joachim
Loeffler, Maarten
Luo, Jun
[J]. INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2011, 21 (03) : 253 - 282
[5] Dumitrescu A., 2004, COMP GEOM-THEOR APPL, P162
[6] Eiter T., 1994, Tech. Rep. CD-TR 94/64
[7] The Frechet Distance Revisited and Extended
Har-Peled, Sariel
Raichel, Benjamin
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2014, 10 (01)
[8] Sriraghavendra R, 2007, PROC INT CONF DOC, P461
[9] van Kreveld M.J., 2015, 31 EUR WORKSH COMP G, P129
[10] Zhu HL, 2010, PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON ADVANCED TEXTILE MATERIALS & MANUFACTURING TECHNOLOGY, P228

← 1 →