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