{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:19:22Z","timestamp":1760440762865},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T00:00:00Z","timestamp":1233273600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s00454-009-9137-7","type":"journal-article","created":{"date-parts":[[2009,1,29]],"date-time":"2009-01-29T14:29:50Z","timestamp":1233239390000},"page":"556-582","source":"Crossref","is-referenced-by-count":25,"title":["Region-Fault Tolerant Geometric Spanners"],"prefix":"10.1007","volume":"41","author":[{"given":"M. A.","family":"Abam","sequence":"first","affiliation":[]},{"given":"M.","family":"de Berg","sequence":"additional","affiliation":[]},{"given":"M.","family":"Farshi","sequence":"additional","affiliation":[]},{"given":"J.","family":"Gudmundsson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,30]]},"reference":[{"issue":"4","key":"9137_CR1","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1016\/j.ejc.2006.04.003","volume":"28","author":"B. Bollob\u00e1s","year":"2007","unstructured":"Bollob\u00e1s, B., Scott, A.: On separating systems. Eur. J. Comb. 28(4), 1068\u20131071 (2007)","journal-title":"Eur. J. Comb."},{"key":"9137_CR2","first-page":"291","volume-title":"SODA\u201993: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P.B. Callahan","year":"1993","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA\u201993: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0291\u2013300. Society for Industrial and Applied Mathematics, Philadelphia (1993)"},{"key":"9137_CR3","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"9137_CR4","doi-asserted-by":"crossref","unstructured":"Chew, L.P.: There is a planar graph almost as good as the complete graph. In SCG\u201986: Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, pp.\u00a0169\u2013177 (1986)","DOI":"10.1145\/10515.10534"},{"key":"9137_CR5","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In STOC\u201987: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp.\u00a056\u201365 (1987)","DOI":"10.1145\/28395.28402"},{"key":"9137_CR6","first-page":"1","volume-title":"SCG\u201903: Proceedings of the 19th Annual ACM Symposium on Computational Geometry","author":"A. Czumaj","year":"2003","unstructured":"Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. In: SCG\u201903: Proceedings of the 19th Annual ACM Symposium on Computational Geometry, pp.\u00a01\u201310. ACM, New York (2003)"},{"key":"9137_CR7","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"G. Das","year":"1997","unstructured":"Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7, 297\u2013315 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9137_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9137_CR9","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1006\/jagm.2000.1135","volume":"38","author":"C.A. Duncan","year":"2001","unstructured":"Duncan, C.A., Goodrich, M.T., Kobourov, S.: Balanced aspect ratio trees: Combining the advances of k-d trees and octrees. J. Algorithms 38, 303\u2013333 (2001)","journal-title":"J. Algorithms"},{"key":"9137_CR10","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/B978-044482537-7\/50010-3","volume-title":"Handbook of Computational Geometry","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp.\u00a0425\u2013461. Elsevier, Amsterdam (2000)"},{"key":"9137_CR11","unstructured":"Fischer, J., Har-Peled, S.: Dynamic well-separated pair decomposition made easy. In CCCG\u201905: Proceedings of the 17th Canadian Conference on Computational Geometry, pp.\u00a0235\u2013238 (2005)"},{"key":"9137_CR12","volume-title":"Handbook on Approximation Algorithms and Metaheuristics","author":"J. Gudmundsson","year":"2007","unstructured":"Gudmundsson, J., Knauer, C.: Dilation and detour in geometric networks. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall, London (2007)"},{"key":"9137_CR13","first-page":"6037","volume":"258","author":"G. Hansel","year":"1964","unstructured":"Hansel, G.: Nombre minimal de contacts de fermeture n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables. C. R. Acad. Sci. Paris 258, 6037\u20136040 (1964). Russian transl., Kibern. Sb. (Nov. Ser.) 5, 47\u201352 (1968)","journal-title":"C. R. Acad. Sci. Paris"},{"key":"9137_CR14","unstructured":"Har-Peled, S.: On the expected complexity of random convex hulls. Technical Report 330\/98, School Math. Sci., Tel-Aviv Univ., Tel-Aviv, Israel (1998)"},{"key":"9137_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/3-540-19487-8_23","volume-title":"SWAT\u201988: Proceedings of the 1st Scandinavian Workshop on Algorithm Theory","author":"J.M. Keil","year":"1988","unstructured":"Keil, J.M.: Approximating the complete Euclidean graph. In: SWAT\u201988: Proceedings of the 1st Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol.\u00a0318, pp.\u00a0208\u2013213. Springer, Berlin (1988)"},{"key":"9137_CR16","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"C. Levcopoulos","year":"2002","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 144\u2013156 (2002)","journal-title":"Algorithmica"},{"key":"9137_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"WADS\u201999: Proceedings of the 6th Workshop on Algorithms and Data Structures","author":"T. Lukovszki","year":"1999","unstructured":"Lukovszki, T.: New results of fault tolerant geometric spanners. In: WADS\u201999: Proceedings of the 6th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol.\u00a01663, pp.\u00a0193\u2013204. Springer, Berlin (1999)"},{"key":"9137_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"key":"9137_CR19","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.: Graph spanners. J.\u00a0Graph Theory 13, 99\u2013116 (1989)","journal-title":"J.\u00a0Graph Theory"},{"key":"9137_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"9137_CR21","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF00535300","volume":"2","author":"A. R\u00e9nyi","year":"1963","unstructured":"R\u00e9nyi, A., Sulanke, R.: \u00dcber die konvexe h\u00fclle von n zuf\u00e4llig gerw\u00e4hten punkten\u00a0I. Z.\u00a0Wahrscheinlichkeitstheor. Verw. Geb. 2, 75\u201384 (1963)","journal-title":"Z.\u00a0Wahrscheinlichkeitstheor. Verw. Geb."},{"key":"9137_CR22","volume-title":"A First Course in Probability","author":"S. Ross","year":"1998","unstructured":"Ross, S.: A First Course in Probability, 5th edn. Prentice-Hall, New York (1998)","edition":"5"},{"key":"9137_CR23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"J.S. Salowe","year":"1991","unstructured":"Salowe, J.S.: Constructing multidimensional spanner graphs. Int. J. Comput. Geom. Appl. 1, 99\u2013107 (1991)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"9137_CR24","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1142\/S0218195992000044","volume":"2","author":"J.S. Salowe","year":"1992","unstructured":"Salowe, J.S.: Enumerating interdistances in space. Int. J. Comput. Geom. Appl. 2(1), 49\u201359 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9137_CR25","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1016\/B978-044482537-7\/50021-8","volume-title":"Handbook of Computational Geometry","author":"M. Smid","year":"2000","unstructured":"Smid, M.: Closest point problems in computational geometry. In: Sack, J.-R. (ed.) Handbook of Computational Geometry, pp.\u00a0877\u2013935. Elsevier, Amsterdam (2000)"},{"issue":"3","key":"9137_CR26","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1137\/0217035","volume":"17","author":"P.M. Vaidya","year":"1988","unstructured":"Vaidya, P.M.: Minimum spanning trees in k-dimensional space. SIAM J. Comput. 17(3), 572\u2013582 (1988)","journal-title":"SIAM J. Comput."},{"key":"9137_CR27","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: An O(nlog\u2009n) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom. 4, 101\u2013115 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9137_CR28","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"P.M. Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in K dimensions. Discrete Comput. Geom. 6(4), 369\u2013381 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"9137_CR29","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In FOCS\u201998: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0320\u2013331 (1998)","DOI":"10.1109\/SFCS.1998.743466"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9137-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9137-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9137-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:36Z","timestamp":1559072856000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9137-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,30]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["9137"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9137-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,30]]}}}