{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:27:34Z","timestamp":1792070854899,"version":"4.4.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540363217","type":"print"},{"value":"9783540363224","type":"electronic"}],"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\/11795490_19","type":"book-chapter","created":{"date-parts":[[2007,1,23]],"date-time":"2007-01-23T12:25:18Z","timestamp":1169555118000},"page":"235-245","source":"Crossref","is-referenced-by-count":27,"title":["Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner of a Unit Disk Graph"],"prefix":"10.1007","author":[{"given":"Edgar","family":"Chavez","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Dobrev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaroslav","family":"Opatrny","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ladislav","family":"Stacho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H\u00e9ctor","family":"Tejeda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorge","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Barriere, L., Fraignaud, P., Narayanan, L., Opatrny, J.: Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In: The Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 19\u201327 (2001)","DOI":"10.1145\/381448.381451"},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-540-27796-5_3","volume-title":"Structural Information and Communication Complexity","author":"P. Boone","year":"2004","unstructured":"Boone, P., Chavez, E., Gleitzky, L., Kranakis, E., Opatrny, J., Salazar, G., Urrutia, J.: Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-hoc Networks. In: Kralovic, R., S\u00fdkora, O. (eds.) SIROCCO 2004. LNCS, vol.\u00a03104, pp. 23\u201334. Springer, Heidelberg (2004)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. In: The Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 48\u201355 (1999)","DOI":"10.1145\/313239.313282"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Broch, J., Maltz, D., Johnson, D., Hu, Y.-C., Jetcheva, J.: A performance comparison of multi-hop wireless ad hoc network routing protocols. In: Mobile Computing and Networking, pp. 85\u201397 (1998)","DOI":"10.1145\/288235.288256"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Datta, S., Stojmenovic, I., Wu, J.: Internal node and shortcut based routing with guaranteed delivery in wireless networks. In: Proc. IEEE Int. Conf. on Distributed Computing and Systems Workshops; Cluster Computing, pp. 461\u2013466 (2001)","DOI":"10.1109\/CDCS.2001.918745"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.2307\/2412323","volume":"18","author":"K. Gabriel","year":"1969","unstructured":"Gabriel, K., Sokal, R.: A new statistical approach to geographic variation analysis. Systematic Zoology\u00a018, 259\u2013278 (1969)","journal-title":"Systematic Zoology"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Geometric Spanner for Routing in Mobile Networks. In: Proceedings of the 2nd ACM International Symposium on Mobile Ad hoc Networking and Computing, pp. 45\u201355 (2001)","DOI":"10.1145\/501422.501424"},{"issue":"9","key":"19_CR9","doi-asserted-by":"publisher","first-page":"1502","DOI":"10.1109\/5.163414","volume":"80","author":"J.W. Jaromczyk","year":"1992","unstructured":"Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE\u00a080(9), 1502\u20131517 (1992)","journal-title":"Proc. IEEE"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M., Gutwin, C.A.: Classes of Graphs which approximate the complete euclidean graph. Discrete Comp. Geom.\u00a07, 13\u201328 (1992)","journal-title":"Discrete Comp. Geom."},{"key":"19_CR11","unstructured":"Kranakis, E., Singh, H., Urrutia, J.: Compass Routing on Geometric Networks. In: Proceedings of 11th Canadian Conference on Computational Geometry, Vancouver, pp. 51\u201354 (August 1999)"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. In: Proc. of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 24\u201333 (2002)","DOI":"10.1145\/570810.570814"},{"key":"19_CR13","unstructured":"Li, X.-Y., Wan, P.-J., Wang, Y., Frieder, O.: Sparse Power Efficient Topology for Wireless Networks. In: HICSS 2002: Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS 2002), vol.\u00a09, p. 296.2 (2002)"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"Computing and Combinatorics","author":"X. Li","year":"2003","unstructured":"Li, X., Wang, Y.: Efficient construction of low weight bounded degree planar spanner. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697. Springer, Heidelberg (2003)"},{"key":"19_CR15","unstructured":"Li, X.-Y., Calinescu, G., Wan, P.-J.: Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks, Distributed construction of planar spanner and routing for ad hoc wireless networks. In: IEEE INFOCOM (2002)"},{"key":"19_CR16","volume-title":"Ad Hoc Networking","year":"2001","unstructured":"Perkins, C.E. (ed.): Ad Hoc Networking. Addison-Wesley, Reading (2001)"},{"issue":"4","key":"19_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","volume":"12","author":"G. Toussaint","year":"1980","unstructured":"Toussaint, G.: The relative neighbourhood graph of a finite planar set. Pattern Recognition\u00a012(4), 261\u2013268 (1980)","journal-title":"Pattern Recognition"},{"issue":"4","key":"19_CR18","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A.C.-C. Yao","year":"1982","unstructured":"Yao, A.C.-C.: On constructing minimum spanning trees in k- dimensional spaces and related problems. SIAM Journal on Computing\u00a011(4), 721\u2013736 (1982)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11795490_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T04:18:27Z","timestamp":1736741907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11795490_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540363217","9783540363224"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11795490_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}