{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T02:10:31Z","timestamp":1747966231757,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642160066"},{"type":"electronic","value":"9783642160073"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16007-3_4","type":"book-chapter","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T08:26:09Z","timestamp":1285143969000},"page":"76-108","source":"Crossref","is-referenced-by-count":12,"title":["Voronoi Graph Matching for Robot Localization and Mapping"],"prefix":"10.1007","author":[{"given":"Jan Oliver","family":"Wallgr\u00fcn","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams \u2013 A survey of a fundamental geometric data structure. ACM Computing Surveys\u00a023(3), 345\u2013405 (1991)","journal-title":"ACM Computing Surveys"},{"key":"4_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/9780470317013","volume-title":"Spatial Tessellations - Concepts and Applications of Voronoi Diagrams","author":"A. Okabe","year":"2000","unstructured":"Okabe, A., Sugihara, K., Chiu, S.N., Boots, B.: Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. John Wiley and Sons, Chichester (2000)"},{"issue":"1","key":"4_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1137\/0210006","volume":"10","author":"D.T. Lee","year":"1981","unstructured":"Lee, D.T., Drysdale III, R.L.S.: Generalization of Voronoi diagrams in the plane. SIAM Journal on Computing\u00a010(1), 73\u201387 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Efficient computation of continuous skeletons. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 18\u201327 (1979)","DOI":"10.1109\/SFCS.1979.15"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0196-6774(85)90021-5","volume":"6","author":"C. \u00d3\u2019D\u00fanlaing","year":"1982","unstructured":"\u00d3\u2019D\u00fanlaing, C., Yap, C.K.: A retraction method for planning the motion of a disc. Journal of Algorithms\u00a06, 104\u2013111 (1982)","journal-title":"Journal of Algorithms"},{"key":"4_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"J.C. Latombe","year":"1991","unstructured":"Latombe, J.C.: Robot Motion Planning. Kluwer Academic Publishers, Dordrecht (1991)"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0004-3702(03)00114-0","volume":"152","author":"E. Remolina","year":"2004","unstructured":"Remolina, E., Kuipers, B.: Towards a general theory of topological maps. Artificial Intelligence\u00a0152(1), 47\u2013104 (2004)","journal-title":"Artificial Intelligence"},{"issue":"1-2","key":"4_CR8","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0004-3702(00)00017-5","volume":"119","author":"B. Kuipers","year":"2000","unstructured":"Kuipers, B.: The Spatial Semantic Hierarchy. Artificial Intelligence\u00a0119(1-2), 191\u2013233 (2000)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1177\/02783640022066770","volume":"19","author":"H. Choset","year":"2000","unstructured":"Choset, H., Burdick, J.: Sensor-based exploration: The Hierarchical Generalized Voronoi Graph. The International Journal of Robotics Research\u00a019(2), 96\u2013125 (2000)","journal-title":"The International Journal of Robotics Research"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Beeson, P., Jong, N.K., Kuipers, B.: Towards autonomous topological place detection using the Extended Voronoi Graph. In: IEEE International Conference on Robotics and Automation (ICRA 2005), pp. 4373\u20134379 (2005)","DOI":"10.1109\/ROBOT.2005.1570793"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Moravec, H., Elfes, A.: High resolution maps from angle sonar. In: Proceedings of the IEEE Conference on Robotics and Automation (ICRA 1985), pp. 116\u2013121 (1985)","DOI":"10.1109\/ROBOT.1985.1087316"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Crowley, J.: World modeling and position estimation for a mobile robot using ultrasonic ranging. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA 1989), pp. 674\u2013680 (1989)","DOI":"10.1109\/ROBOT.1989.100062"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Leonard, J.J., Durrant-Whyte, H.F.: Simultaneous map building and localization for an autonomous mobile robot. In: Proceedings of IEEE\/RSJ International Workshop on Intelligent Robots and Systems, pp. 1442\u20131447 (1991)","DOI":"10.1109\/IROS.1991.174711"},{"key":"4_CR14","volume-title":"Probabilistic Robotics","author":"S. Thrun","year":"2005","unstructured":"Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics. MIT Press, Cambridge (2005)"},{"key":"4_CR15","volume-title":"Tracking and Data Association","author":"Y. Bar-Shalom","year":"1988","unstructured":"Bar-Shalom, Y., Fortmann, T.E.: Tracking and Data Association. Academic Press, London (1988)"},{"key":"4_CR16","volume-title":"Object Recognition by Computer \u2013 The Role of Geometric Constraints","author":"W.E.L. Grimson","year":"1990","unstructured":"Grimson, W.E.L.: Object Recognition by Computer \u2013 The Role of Geometric Constraints. MIT Press, Cambridge (1990)"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Bailey, T., Nieto, J., Nebot, E.: Consistency of the FastSLAM algorithm. In: IEEE International Conference on Robotics and Automation (ICRA 2006), pp. 424\u2013429 (2006)","DOI":"10.1109\/IROS.2006.281644"},{"key":"4_CR18","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/978-3-540-32255-9_23","volume-title":"Spatial Cognition IV, Reasoning, Action, Interaction","author":"J.O. Wallgr\u00fcn","year":"2005","unstructured":"Wallgr\u00fcn, J.O.: Autonomous construction of hierarchical Voronoi-based route graph representations. In: Freksa, C., Knauff, M., Krieg-Br\u00fcckner, B., Nebel, B., Barkowsky, T. (eds.) Spatial Cognition IV. LNCS (LNAI), vol.\u00a03343, pp. 413\u2013433. Springer, Heidelberg (2005)"},{"key":"4_CR19","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"13","author":"A. Sanfeliu","year":"1983","unstructured":"Sanfeliu, A., Fu, K.: A distance measure between attributed relational graph. IEEE Transactions on Systems, Man and Cybernetics\u00a013, 353\u2013362 (1983)","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"issue":"5","key":"4_CR20","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1109\/TPAMI.1986.4767835","volume":"8","author":"M.A. Eshera","year":"1986","unstructured":"Eshera, M.A., Fu, K.S.: An image understanding system using attributed symbolic representation and inexact graph-matching. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a08(5), 604\u2013618 (1986)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"6","key":"4_CR21","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K. Zhang","year":"1989","unstructured":"Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing\u00a018(6), 1245\u20131262 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"4_CR22","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","volume":"42","author":"K. Zhang","year":"1992","unstructured":"Zhang, K., Statman, R., Shasha, D.: On the editing distance between unordered labeled trees. Information Processing Letters\u00a042(3), 133\u2013139 (1992)","journal-title":"Information Processing Letters"},{"issue":"5","key":"4_CR23","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1109\/TPAMI.2004.1273924","volume":"26","author":"T.B. Sebastian","year":"2004","unstructured":"Sebastian, T.B., Klein, P.N., Kimia, B.B.: Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a026(5), 550\u2013571 (2004)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"4_CR24","first-page":"362","volume-title":"Models for the Perception of Speech and Visual Form","author":"H. Blum","year":"1967","unstructured":"Blum, H.: A transformation for extracting new descriptors of shape. In: Wathen-Dunn, W. (ed.) Models for the Perception of Speech and Visual Form, pp. 362\u2013381. MIT Press, Cambridge (1967)"},{"key":"4_CR25","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-540-32255-9_22","volume-title":"Spatial Cognition IV, Reasoning, Action, Interaction","author":"B. Krieg-Br\u00fcckner","year":"2005","unstructured":"Krieg-Br\u00fcckner, B., Frese, U., L\u00fcttich, K., Mandel, C., Mossakowski, T., Ross, R.: Specification of an Ontology for Route Graphs. In: Freksa, C., Knauff, M., Krieg-Br\u00fcckner, B., Nebel, B., Barkowsky, T. (eds.) Spatial Cognition IV. LNCS (LNAI), vol.\u00a03343, pp. 390\u2013412. Springer, Heidelberg (2005)"},{"key":"4_CR26","volume-title":"Hierarchical Voronoi Graphs \u2013 Spatial Representation and Reasoning for Mobile Robots","author":"J.O. Wallgr\u00fcn","year":"2009","unstructured":"Wallgr\u00fcn, J.O.: Hierarchical Voronoi Graphs \u2013 Spatial Representation and Reasoning for Mobile Robots. Springer, Heidelberg (2009)"},{"issue":"3","key":"4_CR27","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0031-3203(94)00105-U","volume":"28","author":"R.L. Ogniewicz","year":"1995","unstructured":"Ogniewicz, R.L., K\u00fcbler, O.: Hierarchic Voronoi Skeletons. Pattern Recognition\u00a028(3), 343\u2013359 (1995)","journal-title":"Pattern Recognition"},{"key":"4_CR28","doi-asserted-by":"crossref","unstructured":"Siddiqi, K., Kimia, B.B.: A shock grammar for recognition. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 507\u2013513 (1996)","DOI":"10.1109\/CVPR.1996.517119"},{"issue":"4","key":"4_CR29","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BF00123352","volume":"6","author":"N. Mayya","year":"1996","unstructured":"Mayya, N., Rajan, V.T.: Voronoi diagrams of polygons: A framework for shape representation. Journal of Mathematical Imaging and Vision\u00a06(4), 355\u2013378 (1996)","journal-title":"Journal of Mathematical Imaging and Vision"},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1109\/70.976019","volume":"17","author":"J. Neira","year":"2001","unstructured":"Neira, J., Tard\u00f3s, J.D.: Data association in stochastic mapping using the joint compability test. IEEE Transactions on Robotics and Automation\u00a017, 890\u2013897 (2001)","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"4_CR32","first-page":"49","volume":"12","author":"P. Mahalanobis","year":"1936","unstructured":"Mahalanobis, P.: On the generalized distance in statistics. Proceedings of the National Institute of Sciences of India\u00a012, 49\u201355 (1936)","journal-title":"Proceedings of the National Institute of Sciences of India"},{"key":"4_CR33","unstructured":"Bailey, T.: Mobile Robot Localisation and Mapping in Extensive Outdoor Environments. PhD thesis, University of Sydney (2001)"},{"key":"4_CR34","series-title":"Springer Tracts in Advanced Robotics","volume-title":"Spatial Representation and Reasoning for Robot Mapping - A Shape-Based Approach","author":"D. Wolter","year":"2008","unstructured":"Wolter, D.: Spatial Representation and Reasoning for Robot Mapping - A Shape-Based Approach. Springer Tracts in Advanced Robotics, vol.\u00a048. Springer, Heidelberg (2008)"},{"issue":"9","key":"4_CR35","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1109\/34.877524","volume":"22","author":"J.H. Lim","year":"2000","unstructured":"Lim, J.H., Leonard, J.J.: Mobile robot relocation from echolocation constraints. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a022(9), 1035\u20131041 (2000)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"Arras, K., Castellanos, J., Schilt, M., Siegwart, R.: Feature-based multi-hypothesis localization and tracking using geometric constraints. Robotics and Autonomous Systems Journal\u00a044(1) (2003)","DOI":"10.1016\/S0921-8890(03)00009-5"},{"key":"4_CR37","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"4_CR38","unstructured":"Montemerlo, M., Thrun, S., Koller, D., Wegbreit, B.: FastSLAM: A factored solution to the simultaneous localization and mapping problem. In: Proceedings of the AAAI National Conference on Artificial Intelligence, pp. 593\u2013598 (2002)"},{"issue":"4","key":"4_CR39","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1177\/027836498600500404","volume":"5","author":"R.C. Smith","year":"1986","unstructured":"Smith, R.C., Cheeseman, P.: On the representation and estimation of spatial uncertainty. The International Journal of Robotics Research\u00a05(4), 56\u201368 (1986)","journal-title":"The International Journal of Robotics Research"},{"issue":"3","key":"4_CR40","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1109\/70.938381","volume":"17","author":"M.G. Dissanayake","year":"2001","unstructured":"Dissanayake, M.G., Newman, P., Clark, S., Durrant-Whyte, H., Csorba, M.: A solution to the simultaneous localization and map building (SLAM) problem. IEEE Transactions on Robotics and Automation\u00a017(3), 229\u2013241 (2001)","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"4_CR41","first-page":"1015","volume-title":"Advances in Neural Information Processing Systems 12","author":"K. Murphy","year":"2000","unstructured":"Murphy, K.: Bayesian map learning in dynamic environments. In: Solla, S.A., Leen, T.K., M\u00fcller, K.R. (eds.) Advances in Neural Information Processing Systems 12, pp. 1015\u20131021. The MIT Press, Cambridge (2000)"},{"key":"4_CR42","volume-title":"Proceedings of the 6th Annual International Symposium on Voronoi Diagrams in Science and Engineering","author":"J.O. Wallgr\u00fcn","year":"2009","unstructured":"Wallgr\u00fcn, J.O.: Matching annotated generalized Voronoi graphs for autonomous robot localization and mapping. In: Anton, F., B\u00e6rentzen, J.A. (eds.) Proceedings of the 6th Annual International Symposium on Voronoi Diagrams in Science and Engineering. IEEE Computer Society, Los Alamitos (2009)"}],"container-title":["Lecture Notes in Computer Science","Transactions on Computational Science IX"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16007-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T23:55:17Z","timestamp":1740527717000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16007-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642160066","9783642160073"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16007-3_4","relation":{},"ISSN":["0302-9743","1866-4741"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1866-4741"}],"subject":[],"published":{"date-parts":[[2010]]}}}