{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T04:39:09Z","timestamp":1713674349019},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T00:00:00Z","timestamp":1470182400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00453-016-0191-2","type":"journal-article","created":{"date-parts":[[2016,8,3]],"date-time":"2016-08-03T12:42:59Z","timestamp":1470228179000},"page":"990-1019","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Connectivity Graphs of Uncertainty Regions"],"prefix":"10.1007","volume":"78","author":[{"given":"Erin","family":"Chambers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"Erickson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Lenchner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff","family":"Sember","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Stege","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Svetlana","family":"Stolpner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Weibel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,3]]},"reference":[{"key":"191_CR1","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0020-0190(99)00107-6","volume":"71","author":"M Abellanas","year":"1999","unstructured":"Abellanas, M., Hurtado, F., Ramos, P.: Structural tolerance and Delaunay triangulation. Inf. Process. Lett. 71, 221\u2013227 (1999)","journal-title":"Inf. Process. Lett."},{"key":"191_CR2","doi-asserted-by":"crossref","unstructured":"Alt, H., Arkin, E., Br\u00f6nnimann, H., Erickson, J., Fekete, S., Knauer, C., Lenchner, J., Mitchell, J., Whittlesey, K.: Minimum-cost coverage of point sets by disks. In: Proceedings of the 22nd ACM Symposium on Computational Geometry (SoCG), pp. 449\u2013458 (2006)","DOI":"10.1145\/1137856.1137922"},{"key":"191_CR3","doi-asserted-by":"crossref","unstructured":"Arkin, E.M., Dieckmann, C., Knauer, C., Mitchell, J.S.B., Polishchuk, V., Schlipf, L., Yang, S.: Convex transversals. In: Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS), pp. 49\u201360 (2011)","DOI":"10.1007\/978-3-642-22300-6_5"},{"issue":"3","key":"191_CR4","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"EM Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197\u2013218 (1994)","journal-title":"Discrete Appl. Math."},{"key":"191_CR5","doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Erickson, A., Fekete, S.P., Lenchner, J., Sember, J., Srinivasan, V., Stege, U., Stolpner, S., Weibel, C., Whitesides, S.: Connectivity graphs of uncertainty regions. In: 21st International Symposium on Algorithms and Computation (ISAAC), number 5307 in Springer LNCS, pp. 434\u2013445 (2010)","DOI":"10.1007\/978-3-642-17514-5_37"},{"key":"191_CR6","unstructured":"Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. Technical Report TR00-054, Electronic Colloquium on Computational Complexity (2000)"},{"issue":"1","key":"191_CR7","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M Berg de","year":"2005","unstructured":"de Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van der Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22\u201336 (2005)","journal-title":"J. Algorithms"},{"key":"191_CR8","doi-asserted-by":"crossref","unstructured":"Ding, H., Xu, J.: Solving the chromatic cone clustering problem via minimum spanning sphere. In: 38th International Colloquium on Automata, Languages and Programming (ICALP), volume 6755 of Springer LNCS, pp. 773\u2013784 (2011)","DOI":"10.1007\/978-3-642-22006-7_65"},{"key":"191_CR9","unstructured":"Disser, Y., Mihal\u00e1k, M., Montanari, S.: Max shortest path for imprecise points. In: 31st European Workshop on Computational Geometry, pp. 184\u2013187 (2015)"},{"key":"191_CR10","doi-asserted-by":"crossref","unstructured":"Disser, Y., Mihal\u00e1k, M., Montanari, S., Widmayer, P.: Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods. In: Proceedings of the 3rd International Symposium on Combinatorial Optimization (ISCO), pp. 208\u2013220 (2014)","DOI":"10.1007\/978-3-319-09174-7_18"},{"key":"191_CR11","doi-asserted-by":"crossref","unstructured":"Dorrigiv, R., Fraser, R., He, M., Kamali, S., Kawamura, A., L\u00f3pez-Ortiz, A., Seco, D.: On minimum- and maximum-weight minimum spanning trees with neighborhoods. In: Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA), pp. 93\u2013106 (2012)","DOI":"10.1007\/978-3-642-38016-7_9"},{"key":"191_CR12","doi-asserted-by":"crossref","unstructured":"Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 473\u2013482 (2003)","DOI":"10.1145\/780542.780612"},{"issue":"3","key":"191_CR13","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0012-365X(83)90128-0","volume":"46","author":"P Duchet","year":"1983","unstructured":"Duchet, P., Hamidoune, Y.O., Vergnas, M.L., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46(3), 319\u2013321 (1983)","journal-title":"Discrete Math."},{"key":"191_CR14","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 38\u201346 (2001)"},{"issue":"2","key":"191_CR15","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.dam.2004.02.018","volume":"145","author":"J Fiala","year":"2005","unstructured":"Fiala, J., Kratochv\u00edl, J., Proskurowski, A.: Systems of distant representatives. Discrete Appl. Math. 145(2), 306\u2013316 (2005)","journal-title":"Discrete Appl. Math."},{"key":"191_CR16","doi-asserted-by":"crossref","unstructured":"Fuchs, B.: On the hardness of range assignment problems. In: Proceedings of the 6th Italian Conference on Algorithms and Complecity (CIAC), pp. 127\u2013138 (2006)","DOI":"10.1007\/11758471_15"},{"key":"191_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"4","key":"191_CR18","first-page":"469","volume":"6","author":"J Gudmundsson","year":"1999","unstructured":"Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nord. J. Comput. 6(4), 469\u2013488 (1999)","journal-title":"Nord. J. Comput."},{"key":"191_CR19","doi-asserted-by":"crossref","unstructured":"Lev-Tov, N., Peleg, D.: Exact algorithms and approximation schemes for base station placement problems. In: Proceedings of the 8th Scandinavian Workshop Algorithm Theory (SWAT), pp. 90\u201399 (2002)","DOI":"10.1007\/3-540-45471-3_10"},{"issue":"4","key":"191_CR20","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.comnet.2004.08.012","volume":"47","author":"N Lev-Tov","year":"2005","unstructured":"Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47(4), 489\u2013501 (2005)","journal-title":"Comput. Netw."},{"issue":"2","key":"191_CR21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"191_CR22","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s00453-008-9174-2","volume":"56","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56, 235\u2013269 (2010)","journal-title":"Algorithmica"},{"key":"191_CR23","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.comgeo.2009.03.007","volume":"43","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. Theory Appl. 43, 419\u2013433 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"191_CR24","doi-asserted-by":"crossref","unstructured":"Mata, C., Mitchell, J.: Approximation algorithms for geometric tour and network design problems. In: Proceedings of the 11th ACM Symposium on Computational Geometry (SoCG), pp. 360\u2013369 (1995)","DOI":"10.1145\/220279.220318"},{"key":"191_CR25","unstructured":"Mitchell, J.S.B.: A PTAS for TSP with neighborhoods among fat regions in the plane. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11\u201318 (2007)"},{"key":"191_CR26","unstructured":"Pan, X., Li, F., Klette, R.: Approximate shortest path algorithms for sequences of pairwise disjoint simple polygons. In: Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG), pp. 175\u2013178 (2010)"},{"issue":"6","key":"191_CR27","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0167-6377(84)90077-4","volume":"2","author":"G Parker","year":"1984","unstructured":"Parker, G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck traveling salesman problem. Oper. Res. Lett. 2(6), 269\u2013272 (1984)","journal-title":"Oper. Res. Lett."},{"key":"191_CR28","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1, 343\u2013353 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"191_CR29","doi-asserted-by":"crossref","unstructured":"Yang, Y., Lin, M., Xu, J., Xie, Y.: Minimum spanning tree with neighborhoods. In: Proceedings of the 3rd Conference on Algorithmic Aspects on Information and Management (AAIM), pp. 306\u2013316. Springer, Berlin, Heidelberg (2007)","DOI":"10.1007\/978-3-540-72870-2_29"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0191-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0191-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0191-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0191-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T03:40:16Z","timestamp":1568259616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0191-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,3]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["191"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0191-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,3]]}}}