Article

Free access

Geometric matching under noise: combinatorial bounds and algorithms

Authors:

Piotr Indyk,

Rajeev Motwani,

Suresh VenkatasubramanianAuthors Info & Claims

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

Pages 457 - 465

Published: 01 January 1999 Publication History

PDF eReader

References

[1]

H. Alt and L. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation, a survey. Technical Report B96-11, Freie Universit#it Berlin, December 1996.

Google Scholar

[2]

E.M. Arkin, K. Kedem, J.S.B. Mitchell, j. Sprinzak, and M. Werman. Matching points into pairwisedisjoint noise regions: Combinatorial bounds and algorithms. ORSA Journal on Computing, 4(4):375-386. 1992.

Google Scholar

[3]

H. Alt, K. Melhorn, H. VCagener, and E. Welzl. Congruence, similiarity, and symmetries of geometric object-s. Discrete Computational Geometry, 3:237-256. 1988.

Google Scholar

[4]

T. Akutsu, H. "}?amaki, and T. Tokuyama. Distribution of distances, and triangles in a point set and algorithms for computing the largest common point set. In Proceedings of the Thirteenth Annual A CM Symposium on Computational Geometry, 1997.

Digital Library

Google Scholar

[5]

D.H. Ballard. Generalizing the Hough Transform to detect arbitrary shapes. Pattern Recognition, 13(2):111-122. 1981.

Google Scholar

[6]

L. Boxer. Point set pattern matching in 3-d. Pattern Recognition Letters. 17(12):1293-1297, 1996.

Digital Library

Google Scholar

[7]

L. P. Chew, D. Dor, A. Efrat, and K. Kedem. Geometric pattern matching in d-dimensional space. In Proc. 2nd Annu. European Sympos. Algorithms, volume 979 of Lecture Notes Comput. Sci., pages 264-279. Springer-Verlag, 1995.

Digital Library

Google Scholar

[8]

K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir. and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Computational Geometry, 5:99-160. 1990.

Google Scholar

[9]

L. Chew. M.T. Goodrich. D.P. Huttenlocher, K. Kedem, J.M. Kleinberg, and D. Kravets. Geometric pattern matching under euclidean motion. In Proceedings of the Filth Canadian Conference on Computational Geometry, pages 151-156. 1993.

Google Scholar

[10]

R. Cole and R. Hariharan. Tree pattern matching and subset matching in randomi:ied O(n log# m) time. In Proceedings of the 29th Annual A CM Symposium on Theory of Computing, 1997.

Digital Library

Google Scholar

[11]

R. Cole, R. Hariharan, and P. Indyk. Tree pattern matching and subset matching in deterministic O(n logz m) Time. In This proceedings, 1999.

Digital Library

Google Scholar

[12]

P.J. de Rezende and D.T. Lee. Point set pattern matching in d-dimensions. Algorithmica, 13:387-404, 1995.

Google Scholar

[13]

A. Efrat. Finding approximate matching of points and segments under translation. Unpublished manuscript, 1995.

Google Scholar

[14]

A. Efrat and A. Itai. Improvements on bottleneck matching and related problems using geometry, in Proceedings of the Twelfth Annual A CM Symposium on Computational Geometry, 1996.

Digital Library

Google Scholar

[15]

P. ErdSs, E. Makai, J. Pach, and J. Spencer. Gaps in difference sets, and the graph of nearly equal distances. Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift (P. Gritzmann and B. Sturmfels, eds.), 4:265-273, 1991.

Google Scholar

[16]

P. ErdSs. On sets of distances of n points. American Mathematical Monthly, 53:248-250. 1946.

Google Scholar

[17]

H. Edelsbmmner, P. Valtr. and E. Welzl. Cutting dense point sets in half. In Proceedings of the Tenth Annual A CM Symposium on Computational Geometry, pages 203-210, I994.

Digital Library

Google Scholar

[18]

P. Firm, D. Halperin, L. E. Kavraki, J. C. Latombe, R. Motwani, C. Shelton, and S. Venkatasul>- ramanian. Geometric manipulation of flexible ligands. LNCS Series- 1996 ACM Workshop on Applied Computational Geometry, 1148:67-78. I996.

Digital Library

Google Scholar

[19]

P. Firm. L. E. Kavraki. J. C. Latombe, R. Motwani, C. Shelton, S. Venkatasubramanian, and A. Yao. Rapid: Randomized pharmacophore identification for drug design. In Proceedings of the Thirteenth Annual A CM Symposium on Computational Geometry, 1997.

Digital Library

Google Scholar

[20]

M.T. Goodrich, 3.B. Mitchell. and M.W. Orletsky. Practical methods for approximate geometric pattern matching under rigid motions. In Proceedings of the Tenth Annual A CM Symposium on Computational Geometry, pages 103-113, 1994.

Digital Library

Google Scholar

[21]

D. P. Huttenlocher, K. Kedem, and J. M. Kleinberg. On dynamic Voronoi diagrams and the minimum Hausdorff distance for points sets under Euclidean motion in the plane. In Proceedings of the Eighth Annual A CM Symposium on Computational Geometry, pages 110-120, 1992.

Digital Library

Google Scholar

[22]

P. J. Heffernan and S. Schirra. Approximate decision algorithms for point set congruence. Computational Geometry: Theory and Applications, 4(3):137- 156, 1994.

Digital Library

Google Scholar

[23]

P. indyk. Deterministic superimposed coding with applications to matching. In Proceedings of the Thirty Eight IEEE Symposium on Foundations of Computer Science, pages 127-136, 1997.

Digital Library

Google Scholar

[24]

National Cancer Institute.2D and 3D Structural data from the Developmental Therapeutics Program, DCTDC, NCI. ht=p: //epnws 1. nc if crf. gov : 2345/ctis3d/3dctatabase/pub s1:ruc, h#tal

Google Scholar

[25]

S. Irani and P. Raghavan. Combinatorial and experimental results for randomized point matching algorithms. In Proceedings of the Twelfth Annual A C# Symposium on Computational Geometry, pages 68-77, 1996.

Digital Library

Google Scholar

[26]

D. Mount, N. Netanyahu, and J. LeMoigne. Improved algorithms for robust point pattern matching and applications to image registration. In Fourteenth A CM Symposium on Computational Geometry, June 1998.

Digital Library

Google Scholar

[27]

S. Muthukrishnan. New results and open problems related to non-standard stringology. In Proceedings of the Symposium on Combinatorial Pattern Matching, pages 298-317, 1995.

Google Scholar

[28]

R. Norel, D. Fischer, H. J. Wolfson, and R. Nussinov. Molecular surface recognition by a computer vision-based technique. Protein Engineering, 7(1) :39-46, 1994.

Google Scholar

[29]

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York., 1985.

Digital Library

Google Scholar

[30]

W.T. Rucklidge. Lower bounds for the complexity of the Hausdorf{ distance. In Proceedings of the Fifth Canadian Conference on Computational Geometry, pages 145-150, 1992.

Google Scholar

[31]

L. Schulman and D. Cardoze. Pattern matching for spatial point sets. In Thirty-ninth Annual Symposium on the Foundations of Computer Science. IEEE, November 1998.

Digital Library

Google Scholar

[32]

E. Szemeredi and W. T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3:381--392. 1983.

Google Scholar

[33]

L. Sz4kely. Crossing numbers and hard ErdSs problems in discrete geometry. Combinatorics, Probability and Computing (to appear), 1997.

Digital Library

Google Scholar

[34]

P. Valtr. Lines, hne-point incidences and crossing families in dense sets. Combinatorica, 16:269-294, 1996.

Google Scholar

Cited By

View all

Rosenke C(2016)The exact complexity of projective image matchingJournal of Computer and System Sciences10.1016/j.jcss.2016.06.00282:8(1360-1387)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.jcss.2016.06.002
Poleksic A(2013)Improved Algorithms for Matching r-Separated Sets with Applications to Protein Structure AlignmentIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.13510:1(226-229)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1109/TCBB.2012.135
Sharathkumar RAgarwal PKarloff HPitassi T(2012)A near-linear time ε-approximation algorithm for geometric bipartite matchingProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214014(385-394)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214014
Show More Cited By

Index Terms

Geometric matching under noise: combinatorial bounds and algorithms
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Statistical template matching under geometric transformations
DGCI'08: Proceedings of the 14th IAPR international conference on Discrete geometry for computer imagery

We present a novel template matching framework for detecting geometrically transformed objects. A template is a simplified representation of the object of interest by a set of pixel groups of any shape, and the similarity between the template and an ...
Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Depending upon the numerical approximation method that may be implemented, hexahedral meshes are frequently preferred to tetrahedral meshes. Because of the layered structure of hexahedral meshes, the automatic generation of hexahedral meshes for ...
Approximate topological matching of quad meshes
Special Issue SMI'2008

In this paper, we study the problem of approximate topological matching for quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two quadrilateral meshes. This study is motivated by applications in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

January 1999

992 pages

ISBN:0898714346

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1999

Check for updates

Qualifiers

Article

Conference

SODA99

Sponsor:

SIGACT
SIAM

SODA99: 1999 10th Conference on Discrete Algorithms

January 17 - 19, 1999

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
60
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rosenke C(2016)The exact complexity of projective image matchingJournal of Computer and System Sciences10.1016/j.jcss.2016.06.00282:8(1360-1387)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.jcss.2016.06.002
Poleksic A(2013)Improved Algorithms for Matching r-Separated Sets with Applications to Protein Structure AlignmentIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.13510:1(226-229)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1109/TCBB.2012.135
Sharathkumar RAgarwal PKarloff HPitassi T(2012)A near-linear time ε-approximation algorithm for geometric bipartite matchingProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214014(385-394)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214014
Fu BWang L(2010)Constant time approximation scheme for largest well predicted subsetProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886866(429-438)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886866
Agarwal PHar-Peled SSharir MWang Y(2010)Hausdorff distance under translation for points and ballsACM Transactions on Algorithms10.1145/1824777.18247916:4(1-26)Online publication date: 3-Sep-2010
https://dl.acm.org/doi/10.1145/1824777.1824791
Bishnu ADas SNandy SBhattacharya B(2010)A simple algorithm for approximate partial point set pattern matching under rigid motionProceedings of the 4th international conference on Algorithms and Computation10.1007/978-3-642-11440-3_10(102-112)Online publication date: 10-Feb-2010
https://dl.acm.org/doi/10.1007/978-3-642-11440-3_10
Hundt CLiśkiewicz M(2009)New Complexity Bounds for Image Matching under Rotation and ScalingProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 557710.5555/3127091.3127103(127-141)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.5555/3127091.3127103
Buchin KBuchin MWang YMathieu C(2009)Exact algorithms for partial curve matching via the Fréchet distanceProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496841(645-654)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496841
Hundt CLikiewicz MNevries R(2009)A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotationTheoretical Computer Science10.1016/j.tcs.2009.09.009410:51(5317-5333)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.09.009
Aiger DMitra NCohen-Or D(2008)4-points congruent sets for robust pairwise surface registrationACM SIGGRAPH 2008 papers10.1145/1399504.1360684(1-10)Online publication date: 11-Aug-2008
https://dl.acm.org/doi/10.1145/1399504.1360684
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Statistical template matching under geometric transformations

Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Approximate topological matching of quad meshes