Fan, Chenglin ;
Filtser, Omrit ;
Katz, Matthew J. ;
Zhu, Binhai
On the General Chain Pair Simplification Problem
Abstract
The Chain Pair Simplification problem (CPS) was posed by Bereg et al. who were motivated by the problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones. In this problem, given two polygonal chains of lengths n and m, the goal is to simplify both of them simultaneously, so that the lengths of the resulting simplifications as well as the discrete Frechet distance between them are bounded. When the vertices of the simplifications are arbitrary (i.e., not necessarily from the original chains), the problem is called General CPS (GCPS).
In this paper we consider for the first time the complexity of GCPS under both the discrete Frechet distance (GCPS3F) and the Hausdorff distance (GCPS2H). (In the former version, the quality of the two simplifications is measured by the discrete Fr'echet distance, and in the latter version it is measured by the Hausdorff distance.) We prove that GCPS3F is polynomially solvable, by presenting an widetildeO((n+m)^6 min{n,m}) time algorithm for the corresponding minimization problem. We also present an O((n+m)^4) 2approximation algorithm for the problem. On the other hand, we show that GCPS2H is NPcomplete, and present an approximation algorithm for the problem.
BibTeX  Entry
@InProceedings{fan_et_al:LIPIcs:2016:6451,
author = {Chenglin Fan and Omrit Filtser and Matthew J. Katz and Binhai Zhu},
title = {{On the General Chain Pair Simplification Problem}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {37:137:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6451},
URN = {urn:nbn:de:0030drops64510},
doi = {10.4230/LIPIcs.MFCS.2016.37},
annote = {Keywords: chain simplification, discrete Frechet distance, dynamic programming, geometric arrangements, protein structural resemblance}
}
19.08.2016
Keywords: 

chain simplification, discrete Frechet distance, dynamic programming, geometric arrangements, protein structural resemblance 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

19.08.2016 