{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:59:27Z","timestamp":1742403567773},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540327554"},{"type":"electronic","value":"9783540327561"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_30","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T06:50:30Z","timestamp":1140159030000},"page":"298-310","source":"Crossref","is-referenced-by-count":6,"title":["An Efficient Approximation Algorithm for Point Pattern Matching Under Noise"],"prefix":"10.1007","author":[{"given":"Vicky","family":"Choi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Navin","family":"Goyal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Megiddo, N.: A Deterministic Poly (log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension. In: Proc. 24th ACM Symp. on Theory of Computing, pp. 327\u2013338 (1992)","DOI":"10.1145\/129712.129744"},{"key":"30_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley Interscience, Hoboken (2000)"},{"key":"30_CR3","first-page":"1629","volume":"12","author":"T. Akutsu","year":"1996","unstructured":"Akutsu, T.: Protein Structure Alignment Using Dynamic Programming and Iterative Improvement. IEICE Trans. on Information and Systems\u00a012, 1629\u20131636 (1996)","journal-title":"IEICE Trans. on Information and Systems"},{"issue":"3","key":"30_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/PL00009388","volume":"20","author":"T. Akutsu","year":"1998","unstructured":"Akutsu, T., Tamaki, H., Tokuyama, T.: Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Sets. Discrete & Computational Geometry\u00a020(3), 307\u2013331 (1998)","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"30_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0166-218X(02)00282-2","volume":"127","author":"T. Akutsu","year":"2003","unstructured":"Akutsu, T., Kanaya, K., Ohyama, A., Fujiyama, A.: Point matching under non-uniform distortions. Discrete Applied Mathematics\u00a0127(1), 5\u201321 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR6","first-page":"121","volume-title":"Handbook of Computational Geometry","author":"H. Alt","year":"1999","unstructured":"Alt, H., Guibas, L.J.: Discrete Geometric Shapes: Matching, Interpolation, and Approximation. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121\u2013153. Elsevier Science Publishers B.V. North-Holland, Amsterdam (1999)"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF02187910","volume":"3","author":"H. Alt","year":"1988","unstructured":"Alt, H., Mehlhorn, K., Wagener, H., Welzl, E.: Congruence, Similarity, and Symmetries of Geometric Objects. Discrete & Computational Geometry\u00a03, 237\u2013256 (1988)","journal-title":"Discrete & Computational Geometry"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45253-2_6","volume-title":"Algorithms - ESA 2000","author":"C. Amb\u00fchl","year":"2000","unstructured":"Amb\u00fchl, C., Chakraborty, S., G\u00e4rtner, B.: Computing Largest Common Point Sets under Approximate Congruence. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 52\u201364. Springer, Heidelberg (2000)"},{"key":"30_CR9","unstructured":"Biswas, S., Chakraborty, S.: Fast Algorithms for Determining Protein Structure Similarity. In: Workshop on Bioinformatics and Computational Biology, Hyderabad, India (2001)"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/3-540-48447-7_26","volume-title":"Algorithms and Data Structures","author":"S. Chakraborty","year":"1999","unstructured":"Chakraborty, S., Biswas, S.: Approximation Algorithms for 3-D Commom Substructure Identification in Drug and Protein Molecules. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 253\u2013264. Springer, Heidelberg (1999)"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Cardoze, D., Schulman, L.: Pattern Matching for Spatial Point Sets. In: Proc. 39th Annual IEEE Symp. on Foundations of Computer Science, pp. 156\u2013165 (1998)","DOI":"10.1109\/SFCS.1998.743439"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/PL00009420","volume":"21","author":"L.P. Chew","year":"1999","unstructured":"Chew, L.P., Dor, D., Efrat, A., Kedem, K.: Geometric Pattern Matching in d-Dimensional Space. Discrete and Computational Geometry\u00a021, 257\u2013274 (1999)","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-540-27801-6_21","volume-title":"Combinatorial Pattern Matching","author":"V. Choi","year":"2004","unstructured":"Choi, V., Goyal, N.: A Combinatorial Shape Matching Algorithm for Rigid Protein Docking. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 285\u2013296. Springer, Heidelberg (2004)"},{"key":"#cr-split#-30_CR14.1","doi-asserted-by":"crossref","unstructured":"Finn, P., Kavraki, L., Latombe, J.-C., Motwani, R., Shelton, C., Venkatasubramanian, S., Yao, A.: RAPID: Randomized Pharmacophore Identification in Drug Design. In: The 13th Symposium on Computational Geometry (1997);","DOI":"10.1145\/262839.262993"},{"key":"#cr-split#-30_CR14.2","doi-asserted-by":"crossref","unstructured":"Finn, P., Kavraki, L., Latombe, J.-C., Motwani, R., Shelton, C., Venkatasubramanian, S., Yao, A.: RAPID: Randomized Pharmacophore Identification in Drug Design. In: The 13th Symposium on Computational Geometry (1997); Computational Geometry: Theory and Applications 10(4) (1998)","DOI":"10.1145\/262839.262993"},{"issue":"1","key":"30_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-003-1043-4","volume":"38","author":"M. Gavrilov","year":"2003","unstructured":"Gavrilov, M., Indyk, P., Motwani, R., Venkatasubramanian, S.: Combinatorial and Experimental Methods for Approximate Point Pattern Matching. Algorithmica\u00a038(1), 59\u201390 (2003)","journal-title":"Algorithmica"},{"issue":"4","key":"30_CR16","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1109\/34.761267","volume":"21","author":"M.T. Goodrich","year":"1999","unstructured":"Goodrich, M.T., Mitchell, J.S.B., Orletsky, M.W.: Approximate Geometric Pattern Matching Under Rigid Motions. IEEE Trans. Pattern Anal. Mach. Intell.\u00a021(4), 371\u2013379 (1999)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Grimson, W.E.L., Huttenlocher, D.P.: On the Sensitivity of Geometric Hashing. In: Proc. of the 3rd Int\u2019l Conference on Computer Vision, pp. 334\u2013338 (1990)","DOI":"10.1109\/ICCV.1990.139544"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Grimson, W.E.L., Huttenlocher, D.P.: On the Sensitivity of Hough Transform for Object Recognition. IEEE Trans. on Pattern Analysis and Machine Intell. 12(3) (1990)","DOI":"10.1109\/34.49052"},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1109\/21.310509","volume":"24","author":"Y. Hecker","year":"1994","unstructured":"Hecker, Y., Bolle, R.: On Geometric Hashing and the Generalized Hough Transform. IEEE Trans. on Systems, Man and Cybernetics\u00a024, 1328\u20131338 (1994)","journal-title":"IEEE Trans. on Systems, Man and Cybernetics"},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0925-7721(94)90004-3","volume":"4","author":"P.J. Heffernan","year":"1994","unstructured":"Heffernan, P.J., Schirra, S.: Approximate Decision Algorithms for Point Set Congruence. Comput. Geom.\u00a04, 137\u2013156 (1994)","journal-title":"Comput. Geom."},{"key":"30_CR21","unstructured":"Indyk, P., Motwani, R., Venkatasubramanian, S.: Geometric Matching under Noise: Combinatorial Bounds and Algorithms. In: The 10th ACM-SIAM Symp. on Discrete Algorithms (1999)"},{"key":"#cr-split#-30_CR22.1","doi-asserted-by":"crossref","unstructured":"Irani, S., Raghavan, P.: Combinatorial and Experimental Results for Randomized Point Matching Algorithms. In: The 12th Symposium on Computational Geometry (1996);","DOI":"10.1145\/237218.237240"},{"key":"#cr-split#-30_CR22.2","doi-asserted-by":"crossref","unstructured":"Comput. Geom. 12(1-2), 17\u201331 (1999)","DOI":"10.1016\/S0925-7721(98)00033-9"},{"issue":"5","key":"30_CR23","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"M. Katz","year":"1997","unstructured":"Katz, M., Sharir, M.: An Expander-based Approach to Geometric Optimization. SIAM J. Comput.\u00a026(5), 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"key":"30_CR24","doi-asserted-by":"crossref","unstructured":"Kenyon, C., Rabani, Y., Sinclair, A.: Low Distortion Maps Between Point Sets. In: Proc. of the 36th Annual ACM Symp. on Theory of Computing (2004)","DOI":"10.1145\/1007352.1007398"},{"key":"30_CR25","unstructured":"Krivelevich, M., Sudakov, B.: Pseudo-random Graphs (preprint), Available at, http:\/\/www.math.tau.ac.il\/~krivelev\/papers.html"},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Lamdan, Y., Wolfson, H.J.: Geometric Hashing: A General and Efficient Model-based Recognition Scheme. In: The 2nd Int\u2019l Conference on Computer Vision, pp. 238\u2013249 (1988)","DOI":"10.1109\/CCV.1988.589995"},{"issue":"2","key":"30_CR27","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1023\/A:1007906812782","volume":"23","author":"C.F. Olson","year":"1997","unstructured":"Olson, C.F.: Efficient Pose Clustering Using a Randomized Algorithm. Int\u2019l J. of Computer Vision\u00a023(2), 131\u2013147 (1997)","journal-title":"Int\u2019l J. of Computer Vision"},{"key":"30_CR28","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1109\/99.641604","volume":"4","author":"H.J. Wolfson","year":"1997","unstructured":"Wolfson, H.J., Rigoutsos, I.: Geometric Hashing: an Overview. IEEE Comput. Science and Engineering\u00a04, 10\u201321 (1997)","journal-title":"IEEE Comput. Science and Engineering"},{"key":"30_CR29","doi-asserted-by":"publisher","first-page":"10495","DOI":"10.1073\/pnas.88.23.10495","volume":"88","author":"R. Nussinov","year":"1991","unstructured":"Nussinov, R., Wolfson, H.J.: Efficient Detection of Three - Dimensional Motifs In Biological Macromolecules by Computer Vision Techniques. Proc. of the Nat\u2019l Academy of Sciences\u00a088, 10495\u201310499 (1991)","journal-title":"Proc. of the Nat\u2019l Academy of Sciences"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T20:18:50Z","timestamp":1555445930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11682462_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}