Computing the Fréchet distance between folded polygons
type: Item
instance of: scholarly article
title: Computing the Fréchet distance between folded polygons
zbMATH Open document ID: 1332.65032
author: Anne Driemel
author: Jessica Sherette
author: Carola Wenk
author: Atlas F. IV. Cook
published in: Computational Geometry
publication date: 2016-01-15T00:00:00Z
review text: The paper deals with the problem of computing the Fréchet distance between folded polygons \(P\) and \(Q\) (a connected polygonal surface for which we have a convex subdivision is called a folded polygon if and only if the dual graph of the convex subdivision is acyclic). To compute the distance, the authors adapt the simple polygon algorithm introduced by \textit{K. Buchin} et al. [Proceedings of the 22nd annual symposium on computational geometry 2006, Sedona, Arizona, USA, June, 05--07, 2006. New York, NY: Association for Computing Machinery. 80--87 (2006; Zbl 1153.68523)]. Because the original algorithm cannot be extended directly, the authors introduce three different methods to adopt it. A core algorithm together with the diagonal monotonicity test and the enhanced diagonal monotonicity test is given right before the introduction of the three methods. The first proposed method is called a fixed-parameter tractable algorithm and uses an algorithm which decides for a fixed placement of \(P\)-diagonals whether the set of \(P\)-diagonals can be mapped within distance \(\varepsilon\) to an untangled set of image curves. A constant-factor approximation algorithm is the second proposed method. In this algorithm, the authors remap the \(P\)-diagonals produced by the diagonal monotonicity test in such a way that the new image curves are within distance at most \(9 \varepsilon\) of their respective \(P\)-diagonals. The last method is restricted to axis-parallel folded polygons (folded polygons for which there exists a convex decomposition of the surface such that all of the interior convex subdivision edges of the surface are parallel to \(x\), \(y\) or \(z\) axis). For this class of polygons, using the proposed algorithm, the authors can compute the Fréchet distance in polynomial time.
reviewed by: Krzysztof Gdawiec
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6531031
zbMATH Keywords: Fréchet distance
zbMATH Keywords: surface comparison
zbMATH Keywords: folded polygons
zbMATH Keywords: polygon algorithm
zbMATH Keywords: monotonicity test
MaRDI profile type: Publication
full work available at URL: j.comgeo.2015.08.002
OpenAlex ID: W1192944040
cites work: Computing the Discrete Fréchet Distance in Subquadratic Time
cites work: The Computational Geometry of Comparing Shapes
cites work: Can we compute the similarity between surfaces?
cites work: Matching planar maps
cites work: COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
cites work: Q4945503
cites work: Comparison of distance measures for planar curves
cites work: Algorithms in real algebraic geometry
cites work: Four Soviets Walk the Dog—with an Application to Alt's Conjecture
cites work: Fréchet Distance of Surfaces: Some Simple Hard Cases
cites work: Q3601525
cites work: Computing the Fréchet Distance between Folded Polygons
cites work: Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts
cites work: Approximating the Fréchet distance for realistic curves in near linear time
cites work: The frechet distance revisited and extended
cites work: Multiplying matrices faster than coppersmith-winograd
DOI: 10.1016/J.COMGEO.2015.08.002
description: scientific article; zbMATH DE number 6531031