On the Chain Pair Simplification Problem

DOI10.1007/978-3-319-21840-3_29MaRDI QIDQ3449833zbMATH OpenOpenAlexFDO

Authors Chenglin Fan, Omrit Filtser, Tim Wylie, Binhai Zhu, Matthew J. Katz

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2457

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones in 3D has led Bereg et al. to pose the Chain Pair Simplification problem (CPS). In this problem, given two polygonal chains $A$ and $B$ of lengths $m$ and $n$, respectively, one needs to simplify them simultaneously, such that each of the resulting simplified chains, $A^{\prime }$ and $B^{\prime }$, is of length at most $k$ and the discrete frechet distance between $A^{\prime }$ and $B^{\prime }$ is at most $delta$, where $k$ and $delta$ are given parameters. In this paper we study the complexity of CPS under the discrete frechet distance (CPS-3F), i.e., where the quality of the simplifications is also measured by the discrete frechet distance. Since CPS-3F was posed in 2008, its complexity has remained open. However, it was believed to be

pc, since CPS under the Hausdorff distance (CPS-2H) was shown to be pc. We first prove that the weighted version of CPS-3F is indeed weakly

pc, even on the line, based on a reduction from the set partition problem. Then, we prove that CPS-3F is actually polynomially solvable, by presenting an $O(m^2{n}^{2}minm,n)$ time algorithm for the corresponding minimization problem. In fact, we prove a stronger statement, implying, for example, that if weights are assigned to the vertices of only one of the chains, then the problem remains polynomially solvable. We also study a few less rigid variants of CPS and present efficient solutions for them. Finally, we present some experimental results that suggest that (the minimization version of) CPS-3F is significantly better than previous algorithms for the motivating biological application.

Recommendations

• On the general chain pair simplification problem
• On a universal chain problem
• scientific article; zbMATH DE number 219236
• Computing optimal 2-3 chains for pairings
• Approximating the Minimum Chain Completion problem
• Publication:3031668
• scientific article; zbMATH DE number 3998771
• The Parallel Simplicity of Compaction and Chaining
• scientific article; zbMATH DE number 177853
• scientific article; zbMATH DE number 2145225

Cites work

• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Four Soviets walk the dog -- with an application to Alt's conjecture
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
• The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Cited in

(6)

• Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
• The Parallel Simplicity of Compaction and Chaining
• Universal approximate simplification under the discrete Fréchet distance
• Consistent simplification of polyline tree bundles
• scientific article; zbMATH DE number 177853 (Why is no real title available?)
• On the general chain pair simplification problem

This page was built for publication: On the Chain Pair Simplification Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449833)