Computing the Frechet distance between piecewise smooth curves

被引：21
|
作者：
Rote, Guenter [1 ]
机构：
[1] Free Univ Berlin, Inst Informat, D-14195 Berlin, Germany
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2007年 / 37卷 / 03期
关键词：
shape matching;
D O I：
10.1016/j.comgeo.2005.01.004
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider the Frechet distance between two curves which are given as a sequence of m + n curved pieces. If these pieces are sufficiently well-behaved, we can compute the Frechet distance in O(mn log(mn)) time. The decision version of the problem can be solved in O(mn) time. The results are based on an analysis of the possible intersection patterns between circles and arcs of bounded curvature. (C) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：162 / 174
页数：13
相关论文
共 50 条
  • [1] COMPUTING THE FRECHET DISTANCE BETWEEN 2 POLYGONAL CURVES
    ALT, H
    GODAU, M
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (1-2) : 75 - 91
  • [2] Computing the Frechet distance between uncertain curves in one dimension
    Buchin, Kevin
    Loeffler, Maarten
    Ophelders, Tim
    Popov, Aleksandr
    Urhausen, Jerome
    Verbeek, Kevin
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2023, 109
  • [3] Computing the Frechet Distance Between Uncertain Curves in One Dimension
    Buchin, Kevin
    Loeffler, Maarten
    Ophelders, Tim
    Popov, Aleksandr
    Urhausen, Jerome
    Verbeek, Kevin
    ALGORITHMS AND DATA STRUCTURES, WADS 2021, 2021, 12808 : 243 - 257
  • [4] Generalized Frechet distance between curves
    Bogacki, P
    Weinstein, SE
    MATHEMATICAL METHODS FOR CURVES AND SURFACES II, 1998, : 25 - 32
  • [5] Computing the Frechet Distance between Folded Polygons
    Cook, Atlas F.
    Driemel, Anne
    Har-Peled, Sariel
    Sherette, Jessica
    Wenk, Carola
    ALGORITHMS AND DATA STRUCTURES, 2011, 6844 : 267 - +
  • [6] Computing the Frechet distance between simple polygons
    Buchin, Kevin
    Buchin, Maike
    Wenk, Carola
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2008, 41 (1-2): : 2 - 20
  • [7] Computing the Frechet Distance Between Polygons with Holes
    Nayyeri, Amir
    Sidiropoulos, Anastasios
    AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 : 997 - 1009
  • [8] Computing the Frechet distance between folded polygons
    Cook, Atlas F.
    Driemel, Anne
    Sherette, Jessica
    Wenk, Carola
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 50 : 1 - 16
  • [9] Fast Frechet Distance between Curves with Long Edges
    Gudmundsson, Joachim
    Mirzanezhad, Majid
    Mohades, Ali
    Wenk, Carola
    PROCEEDINGS OF THE 3RD INTERNATIONAL WORKSHOP ON INTERACTIVE AND SPATIAL COMPUTING (IWISC 18), 2018, : 52 - 58
  • [10] Frechet distance for curves, revisited
    Aronov, Boris
    Har-Peled, Sariel
    Knauer, Christian
    Wang, Yusu
    Wenk, Carola
    ALGORITHMS - ESA 2006, PROCEEDINGS, 2006, 4168 : 52 - 63
12345