the discrete Frechet distance with applications.

详细信息   

• 作者：Wylie ; Timothy Randall.
• 学历：Ph.D.
• 年：2013
• 导师：Zhu, Binhai,eadvisorRoss, Rockfordecommittee memberMumey, Brendanecommittee memberYang, Qingecommittee memberAngryk, Rafalecommittee memberGao, Hongweiecommittee member
• 毕业院校：Montana State University
• Department：Computer Science
• ISBN：9781303308369
• CBH：3590845
• Country：USA
• 语种：English
• FileSize：1529603
• Pages：127

文摘

Modern computational geometry plays a critical role across a vast number of diverse research fields where theoretical results for provably efficient algorithms are necessary. Many of these problems are based on matching geometric objects or finding paths through given points with polygonal curves. This work focuses on the study and application of polygonal curves with respect to the discrete Fr&eacute；chet distance. We look at protein backbone structure alignment, comparison, and simplification. Previous work has largely focused on using the RMSD Root Mean Square Deviation) distance measure. We build upon recent work demonstrating the benefits of the discrete Fr&eacute；chet distance in this area, and present the first alignment algorithm based on the discrete Fr&eacute；chet distance and compare our results with previous work. To address visualization, the chain pair simplification problem CPS-3F) was proposed in 2008 to simultaneously simplify two chains with respect to each other under the discrete Fr&eacute；chet distance. The complexity of CPS-3F is unknown, so we present algorithms to address CPS-3F instances efficiently. We give a greedy backtracking heuristic and two factor-2 approximation algorithms for CPS-3F. We give empirical results for the heuristic and for one of the approximations, CPS-3F＋. Further, we provide dynamic programming solutions for many other CPS-3F properties. Chain pair simplification based on the Hausdorff distance CPS-2H) is known to be NP- complete, and we prove the constrained version CPS-2H＋) is also NP-complete. We then investigate the discrete map matching and discrete set-chain matching problems and variations of them. The map matching problem is to find a path in a graph with a minimal Fr&eacute；chet distance to a given polygonal line. The set-chain matching problem attempts to find another polygonal curve with nodes from a given point set. We prove the complexities of many of these problem variations when given a maximal number of vertices or points allowed, and when the paths are unique. Some of which are NP-complete and others we give a dynamic programming solution to. Finally, many of the algorithms that we developed have also been implemented and released as a software library, named The Fr&eacute；chet-based Protein Alignment &； Comparison Toolkit FPACT).