Can I read On the Chain Pair Simplification Problem on EtoBox?

On the Chain Pair Simplification Problem by Fan, Chenglin; Filtser, Omrit; Katz, Matthew J.; Wylie, Tim; Zhu, Binhai is a scholarly article available to read on EtoBox.

What is On the Chain Pair Simplification Problem about?

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'$ and $B'$, is of length at most $k$ and the discrete \frechet\ distance between $A'$ and $B'$ 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 \npc, since CPS under the Hausdorff distance (CPS-2H) was shown to be \npc. We first prove that the weighted version of CPS-3F is indeed weakly \npc\, 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^2n^2\min\{m,n\})$ time algorithm for the corresponding m

Author

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

Published

2014

Language

EN