Geometric matching under noise: combinatorial bounds and algorithms

Keywords

Algorithm, Matching (statistics), Point set registration, Pattern matching, Mathematics

References

• Generalizing the Hough transform to detect arbitrary shapesD.H. Ballard — 1981
• Improved algorithms for robust point pattern matching and applications to image registrationDavid M. Mount, Nathan S. Netanyahu, Jacqueline Le Moigne — 1998
• Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point SetsTatsuya Akutsu, Hisao Tamaki, Takeshi Tokuyama — 1997
• Approximate decision algorithms for point set congruencePaul J. Heffernan, Stefan Schirra — 1992
• On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the planeDaniel P. Huttenlocher, Klara Kedem, Jon Kleinberg — 1992
• Improvements on bottleneck matching and related problems using geometryAlon Efrat, Alon Itai — 1996
• Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version)Michael T. Goodrich, Joseph S. B. Mitchell, Mark Walter Orletsky — 1994
• Cutting dense point sets in halfHerbert Edelsbrunner, Pável Valtr, Emo Welzl — 1994
• Congruence, similarity, and symmetries of geometric objectsHans Wilhelm Alt, Kurt Mehlhorn, Hubert Wagener — 1987
• Combinatorial complexity bounds for arrangements of curves and spheresKenneth L. Clarkson, Herbert Edelsbrunner, Leonidas Guibas — 1990
• Combinatorial and experimental results for randomized point matching algorithmsSandy Irani, Prabhakar Raghavan — 1996
• Tree pattern matching and subset matching in randomized O(nlog3m) timeRichard Cole, Ramesh Hariharan — 1997
• Point set pattern matching in 3-DLaurence Boxer — 1996
• Geometric Pattern Matching Under Euclidean MotionL. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher — 1993
• Lines, line-point incidences and crossing families in dense setsPável Valtr — 1996
• Molecular surface recognition by a computer vision-based technique.Raquel Norel, Daniel Fischer, Haim J. Wolfson — 1994
• Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and AlgorithmsEsther M. Arkin, Klara Kedem, Joseph S. B. Mitchell — 1992
• RAPID: randomized pharmacophore identification for drug designPaul W. Finn, Lydia E. Kavraki, J.-C. Latombe — 1997
• Deterministic superimposed coding with applications to pattern matchingPiotr Indyk — 1997
• Crossing Numbers and Hard Erdős Problems in Discrete GeometryŁászló A. Székely — 1997

Cited by

• Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing MotifsJ. Donald Johnson, R.L. Jolley — 2005
• Approximate Matching of Digital Point Sets Using a Novel Angular TreeAbdelhafid Zeghbib, Frank Palis, Fathi Ben Ouezdou — 2009
• Mining Spatial Motifs from Protein Structure GraphsJun Huan, Wei Wang, Deepak Bandyopadhyay — 2003
• Approximate nearest neighbor algorithms for Hausdorff metrics via embeddingsMartı́n Farach-Colton, Piotr Indyk — 1999
• Dense point sets have sparse Delaunay triangulationsJeff Erickson — 2001
• Geometry-based methods for protein function predictionBrian Yuan Chen — 2006
• Polynomials: a new tool for length reduction in binary discrete convolutionsAmihood Amir, Oren Kapah, Ely Porat — 2014
• A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotationChristian Hundt, Maciej Liśkiewicz, Ragnar Nevries — 2009
• Accurate Classification of Protein Structural Families Using Coherent Subgraph AnalysisJun Huan, Wei Wang, Amber R. Washington — 2003
• Verifying candidate matches in sparse and wildcard matchingRichard Cole, Ramesh Hariharan — 2002
• Computational Approaches to Drug DesignPaul W. Finn, Lydia E. Kavraki — 1999
• New complexity bounds for image matching under rotation and scalingChristian Hundt, Maciej Liśkiewicz — 2009
• Exact algorithms for partial curve matching via the Fréchet distanceKevin Buchin, Maike Buchin, Yusu Wang — 2009
• Constant time approximation scheme for largest well predicted subsetBin Fu, Lusheng Wang — 2010
• Approximate congruence in nearly linear timePiotr Indyk, Suresh Venkatasubramanian — 2000
• Combinatorial and Experimental Methods for Approximate Point Pattern MatchingMartin Gavrilov, Piotr Indyk, Rajeev Motwani — 2003
• A near-linear time ε-approximation algorithm for geometric bipartite matchingR. Sharathkumar, Pankaj K. Agarwal — 2012
• Nice Point Sets Can Have Nasty Delaunay TriangulationsJeff Erickson — 2001
• The MASH Pipeline for Protein Function Prediction and an Algorithm for the Geometric Refinement of 3D MotifsBrian Y. Chen, Viacheslav Y. Fofanov, Drew Bryant — 2007
• Constrained Branch-and-Bound algorithm for image registrationJianqiu Jin, Zhang-ye Wang, Qunsheng Peng — 2005

Related papers

• Pattern matching for spatial point setsDavid E. Cardoze, Leonard J. Schulman — 1998
• Congruence, similarity, and symmetries of geometric objectsHans Wilhelm Alt, Kurt Mehlhorn, Hubert Wagener — 1987
• Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version)Michael T. Goodrich, Joseph S. B. Mitchell, Mark Walter Orletsky — 1994
• Approximate decision algorithms for point set congruencePaul J. Heffernan, Stefan Schirra — 1994
• Geometric Pattern Matching Under Euclidean MotionL. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher — 1993
• On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the planeDaniel P. Huttenlocher, Klara Kedem, Jon Kleinberg — 1992
• RAPID: randomized pharmacophore identification for drug designPaul W. Finn, Lydia E. Kavraki, J.-C. Latombe — 1997
• Geometric pattern matching: a performance studyMartin Gavrilov, Piotr Indyk, Rajeev Motwani — 1999
• Pattern matching in a digitized imageGad M. Landau, Uzi Vishkin — 1992