{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:24:18Z","timestamp":1725470658884},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540390985"},{"type":"electronic","value":"9783540391012"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11847250_16","type":"book-chapter","created":{"date-parts":[[2006,9,13]],"date-time":"2006-09-13T15:43:02Z","timestamp":1158162182000},"page":"175-183","source":"Crossref","is-referenced-by-count":6,"title":["On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching"],"prefix":"10.1007","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos","family":"Giannopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Knauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"16_CR1","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/S0925-7721(97)00010-2","volume":"9","author":"T. Akutsu","year":"1998","unstructured":"Akutsu, T.: On determining the congruence of point sets in d-dimensions. Comput. Geom. Theory Appl.\u00a09(4), 247\u2013256 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"16_CR2","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 (1999)"},{"key":"16_CR3","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 Comput. Geom.\u00a03, 237\u2013256 (1988)","journal-title":"Discrete Comput. Geom."},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/3-540-45253-2_11","volume-title":"Algorithms - ESA 2000","author":"P. Bra\u00df","year":"2000","unstructured":"Bra\u00df, P.: Exact point pattern matching and the number of congruent triangles in a three-dimensional pointset. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 112\u2013119. Springer, Heidelberg (2000)"},{"issue":"1","key":"16_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1142\/S0218195902000761","volume":"12","author":"P. Bra\u00df","year":"2002","unstructured":"Bra\u00df, P., Knauer, C.: Testing the congruence of d-dimensional point sets. Int. J. of Comp. Geom. Appl.\u00a012(1), 115\u2013124 (2002)","journal-title":"Int. J. of Comp. Geom. Appl."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/0-387-25592-3_2","volume-title":"Graph Theory and Combinatorial Optimization, Gerad 25th Anniversary","author":"P. Bra\u00df","year":"2005","unstructured":"Bra\u00df, P., Pach, J.: Problems and results on geometric patterns. In: Avis, D., Hertz, A., Marcotte, O. (eds.) Graph Theory and Combinatorial Optimization, Gerad 25th Anniversary, pp. 17\u201336. Springer, Heidelberg (2005)"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/11561071_47","volume-title":"Algorithms \u2013 ESA 2005","author":"S. Cabello","year":"2005","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C., Rote, G.: Matching point sets with respect to the earth mover\u2019s distance. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 520\u2013531. Springer, Heidelberg (2005)"},{"issue":"2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J. Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation\u00a0201(2), 216\u2013231 (2005)","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"Chew, L.P., Dor, D., Efrat, A., Kedem, K.: Geometric pattern matching in d-dimensional space. Discrete Comput. Geom.\u00a021 (1999)","key":"16_CR9","DOI":"10.1007\/PL00009420"},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0925-7721(95)00047-X","volume":"7","author":"L.P. Chew","year":"1997","unstructured":"Chew, L.P., Goodrich, M., Huttenlocher, D.P., Kedem, K., Kleinberg, J.M., Kravets, D.: Geometric pattern matching under Euclidean motion. Comput. Geom. Theory Appl.\u00a07, 113\u2013124 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"doi-asserted-by":"crossref","unstructured":"Cohen, S.D., Guibas, L.J.: The Earth Mover\u2019s Distance under transformation sets. In: Proceedings of the 7th IEEE International Conference on Computer Vision, pp. 173\u2013187 (September 1999)","key":"16_CR11","DOI":"10.1109\/ICCV.1999.790393"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF01293487","volume":"13","author":"P.J. Rezende de","year":"1995","unstructured":"de Rezende, P.J., Lee, D.T.: Point set matching in d-dimensions. Algorithmica\u00a013, 387\u2013404 (1995)","journal-title":"Algorithmica"},{"key":"16_CR13","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.J.: Geometry helps in bottleneck matching and related problems. Algorithmica\u00a031, 1\u201328 (2001)","journal-title":"Algorithmica"},{"key":"16_CR14","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer, Heidelberg (2006)"},{"unstructured":"Hagedoorn, M., Veltkamp, R.C.: State-of-the-art in shape matching. Technical Report UU-CS-1999-027, Institute of Information and Computing Sciences, Utrecht University, The Netherlands (1999)","key":"16_CR15"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF02189323","volume":"9","author":"D.P. Huttenlocher","year":"1993","unstructured":"Huttenlocher, D.P., Kedem, K., Sharir, M.: The upper envelope of Voronoi surfaces and its applications. Discrete Comput. Geom.\u00a09, 267\u2013291 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"16_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/11561071_41","volume-title":"Algorithms \u2013 ESA 2005","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 448\u2013459. Springer, Heidelberg (2005)"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM\u00a031, 114\u2013127 (1984)","journal-title":"J. ACM"},{"issue":"3-4","key":"16_CR19","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0747-7171(08)80067-3","volume":"10","author":"N. Megiddo","year":"1990","unstructured":"Megiddo, N.: On the complexity of some geometric problems in unbounded dimension. J. Symb. Comput.\u00a010(3-4), 327\u2013334 (1990)","journal-title":"J. Symb. Comput."},{"key":"16_CR20","first-page":"112","volume-title":"Proc. of the 16th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA)","author":"C. Papadimitriou","year":"2005","unstructured":"Papadimitriou, C., Safra, S.: The complexity of low-distortion embeddings between point sets. In: Proc. of the 16th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 112\u2013118. SIAM, Philadelphia (2005)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11847250_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:42:06Z","timestamp":1605642126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11847250_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540390985","9783540391012"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11847250_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}