{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T06:53:53Z","timestamp":1758264833464,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642121999"},{"type":"electronic","value":"9783642122002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12200-2_40","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T13:53:05Z","timestamp":1271857985000},"page":"456-467","source":"Crossref","is-referenced-by-count":1,"title":["Matching Points with Things"],"prefix":"10.1007","author":[{"given":"Greg","family":"Aloupis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e9bastien","family":"Collette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin L.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muriel","family":"Dulieu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruy","family":"Fabila-Monroy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vi","family":"Hart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ferran","family":"Hurtado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Saumell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Seara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Perouz","family":"Taslakian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"40_CR1","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/BF01187037","volume":"9","author":"P. Agarwal","year":"1993","unstructured":"Agarwal, P., Aronov, B., Sharir, M., Suri, S.: Selecting distances in the plane. Algorithmica\u00a09(5), 495\u2013514 (1993)","journal-title":"Algorithmica"},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1016\/j.comgeo.2008.12.005","volume":"42","author":"O. Aichholzer","year":"2009","unstructured":"Aichholzer, O., Bereg, S., Dumitrescu, A., Garc\u00eda, A., Huemer, C., Hurtado, F., Kano, M., M\u00e1rquez, A., Rappaport, D., Smorodinsky, S., Souvaine, D., Urrutia, J., Wood, D.R.: Compatible geometric matchings. Computational Geometry: Theory and Applications\u00a042, 617\u2013626 (2009)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"40_CR3","unstructured":"Aichholzer, O., Cabello, S., Fabila-Monroy, R., Flores-Penaloza, D., Hackl, T., Huemer, C., Hurtado, F., Wood, D.R.: Edge-Removal and Non-Crossing Configurations in Geometric Graphs. In: Proceedings of 24th European Conference on Computational Geometry, pp. 119\u2013122 (2008)"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Alt, H., Guibas, L.: Discrete geometric shapes: Matching, interpolation, and approximation. In: Handbook of computational geometry, pp. 121\u2013154 (1999)","DOI":"10.1016\/B978-044482537-7\/50004-8"},{"key":"40_CR5","unstructured":"Arkin, E., Kedem, K., Mitchell, J., Sprinzak, J., Werman, M.: Matching points into noise regions: combinatorial bounds and algorithms. In: Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pp. 42\u201351 (1991)"},{"issue":"9","key":"40_CR6","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers\u00a028(9), 643\u2013647 (1979)","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"40_CR7","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.comgeo.2006.10.001","volume":"39","author":"S. Cabello","year":"2008","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C., Rote, G.: Matching point sets with respect to the Earth Mover\u2019s Distance. Computational Geometry: Theory and Applications\u00a039(2), 118\u2013133 (2008)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Cardoze, D., Schulman, L.: Pattern matching for spatial point sets. In: Proceedings. 39th Annual Symposium on Foundations of Computer Science (FOCS), 1998, pp. 156\u2013165 (1998)","DOI":"10.1109\/SFCS.1998.743439"},{"issue":"1","key":"40_CR9","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete and Computational Geometry\u00a06(1), 485\u2013542 (1991)","journal-title":"Discrete and Computational Geometry"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/PL00009420","volume":"21","author":"L. Chew","year":"1999","unstructured":"Chew, L., Dor, D., Efrat, A., Kedem, K.: Geometric pattern matching in d-dimensional space. Discrete and Computational Geometry\u00a021(2), 257\u2013274 (1999)","journal-title":"Discrete and Computational Geometry"},{"issue":"1-2","key":"40_CR11","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0925-7721(95)00047-X","volume":"7","author":"L. Chew","year":"1997","unstructured":"Chew, L., Goodrich, M., Huttenlocher, D., Kedem, K., Kleinberg, J., Kravets, D.: Geometric pattern matching under Euclidean motion. Computational Geometry: Theory and Applications\u00a07(1-2), 113\u2013124 (1997)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"40_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/3-540-55706-7_28","volume-title":"Algorithm Theory - SWAT \u201992","author":"L. Chew","year":"1992","unstructured":"Chew, L., Kedem, K.: Improvements on geometric pattern matching problems. In: Nurmi, O., Ukkonen, E. (eds.) SWAT 1992. LNCS, vol.\u00a0621, pp. 318\u2013325. Springer, Heidelberg (1992)"},{"key":"40_CR13","unstructured":"Cohen, S.: Finding color and shape patterns in images. PhD thesis, Stanford University, Department of Computer Science (1999)"},{"issue":"4","key":"40_CR14","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1089\/cmb.2006.13.979","volume":"13","author":"J. Colannino","year":"2006","unstructured":"Colannino, J., Damian, M., Hurtado, F., Iacono, J., Meijer, H., Ramaswami, S., Toussaint, G.: An O(n logn)-time algorithm for the restriction scaffold assignment problem. Journal of Computational Biology\u00a013(4), 979\u2013989 (2006)","journal-title":"Journal of Computational Biology"},{"issue":"1","key":"40_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0016-8","volume":"31","author":"A. Efrat","year":"2001","unstructured":"Efrat, A., Itai, A., Katz, M.: Geometry helps in bottleneck matching and related problems. Algorithmica\u00a031(1), 1\u201328 (2001)","journal-title":"Algorithmica"},{"key":"40_CR16","unstructured":"Formella, A.: Approximate point set match for partial protein structure alignment. In: Proceedings of Bioinformatics: Knowledge Discovery in Biology (BKDB 2005), Facultade Ciencias Lisboa da Universidade de Lisboa, pp. 53\u201357 (2005)"},{"key":"40_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/3-540-47977-5_47","volume-title":"Computer Vision - ECCV 2002","author":"P. Giannopoulos","year":"2002","unstructured":"Giannopoulos, P., Veltkamp, R.: A pseudo-metric for weighted point sets. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) ECCV 2002. LNCS, vol.\u00a02352, pp. 715\u2013730. Springer, Heidelberg (2002)"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Grauman, K., Darrell, T.: Fast contour matching using approximate earth mover\u2019s distance. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 220\u2013227 (2004)","DOI":"10.1109\/CVPR.2004.1315035"},{"key":"40_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/3-540-57155-8_263","volume-title":"Algorithms and Data Structures","author":"P. Heffernan","year":"1993","unstructured":"Heffernan, P.: Generalized approximate algorithms for point set congruence. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 373\u2013373. Springer, Heidelberg (1993)"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Heffernan, P., Schirra, S.: Approximate decision algorithms for point set congruence. In: Proceedings of the eighth annual Symposium on Computational geometry, pp. 93\u2013101 (1992)","DOI":"10.1145\/142675.142697"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Huttenlocher, D., Kedem, K.: Efficiently computing the Hausdorff distance for point sets under translation. In: Proceedings of the Sixth ACM Symposium on Computational Geometry, pp. 340\u2013349 (1990)","DOI":"10.1145\/98524.98599"},{"key":"40_CR22","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/978-3-642-55566-4_25","volume":"25","author":"A. Kaneko","year":"2003","unstructured":"Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane\u2014a survey. Discrete & Computational Geometry\u00a025, 551\u2013570 (2003)","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"40_CR23","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM Journal on Computing\u00a012(1), 28\u201335 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR24","volume-title":"Matching theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching theory. Elsevier Science Ltd., Amsterdam (1986)"},{"key":"40_CR25","series-title":"Lecture Notes in Computer Science","first-page":"246","volume-title":"Discrete and Computational Geometry","author":"D. Rappaport","year":"2002","unstructured":"Rappaport, D.: Tight bounds for visibility matching of f-equal width objects. In: Akiyama, J., Kano, M. (eds.) JCDCG 2002. LNCS, vol.\u00a02866, pp. 246\u2013250. Springer, Heidelberg (2002)"},{"key":"40_CR26","unstructured":"Typke, R., Giannopoulos, P., Veltkamp, R., Wiering, F., Van Oostrum, R.: Using transportation distances for measuring melodic similarity. In: Proceedings of the 4th International Conference on Music Information Retrieval (ISMIR 2003), pp. 107\u2013114 (2003)"},{"key":"40_CR27","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/62212.62253","volume-title":"STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing","author":"P. Vaidya","year":"1988","unstructured":"Vaidya, P.: Geometry helps in matching. In: STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 422\u2013425. ACM, New York (1988)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2010: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12200-2_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T03:12:59Z","timestamp":1740021179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}