Computing the Fréchet distance between folded polygons (Q904083)

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.