{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T14:50:16Z","timestamp":1668005416291},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,6,12]],"date-time":"2009-06-12T00:00:00Z","timestamp":1244764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,7]]},"DOI":"10.1007\/s00453-009-9329-9","type":"journal-article","created":{"date-parts":[[2009,6,11]],"date-time":"2009-06-11T10:33:54Z","timestamp":1244716434000},"page":"627-652","source":"Crossref","is-referenced-by-count":4,"title":["Minimum Weight Convex Steiner Partitions"],"prefix":"10.1007","volume":"60","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,6,12]]},"reference":[{"issue":"3","key":"9329_CR1","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(05)80059-5","volume":"48","author":"M.W. Bern","year":"1994","unstructured":"Bern, M.W., Eppstein, D., Gilbert, J.R.: Provably good mesh generation. J. Comput. Syst. Sci. 48(3), 384\u2013409 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"9329_CR2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.tcs.2004.05.019","volume":"324","author":"P. Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Competitive online routing in geometric graphs. Theor. Comput. Sci. 324(2\u20133), 273\u2013288 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9329_CR3","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1137\/S0097539700369387","volume":"33","author":"P. Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Online routing in triangulations. SIAM J. Comput. 33(4), 937\u2013951 (2004)","journal-title":"SIAM J. Comput."},{"key":"9329_CR4","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1023\/A:1012319418150","volume":"7","author":"P. Bose","year":"2001","unstructured":"Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wirel. Netw. 7, 609\u2013616 (2001)","journal-title":"Wirel. Netw."},{"issue":"4","key":"9329_CR5","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1142\/S021819590200089X","volume":"12","author":"P. Bose","year":"2002","unstructured":"Bose, P., Brodnik, A., Carlsson, S., Demaine, E.D., Fleischer, R., Lopez-Ortiz, A., Morin, P., Munro,\u00a0I.: Online routing in convex subdivisions. Intern. J. Comput. Geom. & Appl. 12(4), 283\u2013295 (2002)","journal-title":"Intern. J. Comput. Geom. & Appl."},{"key":"9329_CR6","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00453-005-1168-8","volume":"42","author":"P. Bose","year":"2005","unstructured":"Bose, P., Gudmundsson, J., Smid, M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249\u2013264 (2005)","journal-title":"Algorithmica"},{"key":"9329_CR7","first-page":"38","volume-title":"Proc. of the 11th Sympos. on Theory of Computing","author":"B. Chazelle","year":"1979","unstructured":"Chazelle, B., Dobkin, D.P.: Decomposing a polygon into its convex parts. In: Proc. of the 11th Sympos. on Theory of Computing, pp. 38\u201348. ACM, New York (1979)"},{"key":"9329_CR8","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/BF01377183","volume":"12","author":"B. Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L.J., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12, 54\u201368 (1994)","journal-title":"Algorithmica"},{"key":"9329_CR9","first-page":"17","volume-title":"Proc. of the 2nd Sympos. on Discrete Algorithms","author":"K.L. Clarkson","year":"1991","unstructured":"Clarkson, K.L.: Approximation algorithms for planar traveling salesman tours and minimum-length triangulations. In: Proc. of the 2nd Sympos. on Discrete Algorithms, pp. 17\u201323. ACM, New York (1991)"},{"key":"9329_CR10","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., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9329_CR11","unstructured":"de Wet, P.O.: Geometric Steiner minimal trees. Ph.D. thesis, University of South Africa (2008). http:\/\/etd.unisa.ac.za\/ETD-db\/theses\/available\/etd-08052008-130058\/unrestricted\/thesis.pdf"},{"key":"9329_CR12","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01758755","volume":"7","author":"D.-Z. Du","year":"1992","unstructured":"Du, D.-Z., Hwang, F.K.: A proof of Gilbert-Pollak\u2019s conjecture on the Steiner ratio. Algorithmica 7, 121\u2013135 (1992)","journal-title":"Algorithmica"},{"key":"9329_CR13","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.jda.2008.07.007","volume":"7","author":"A. Dumitrescu","year":"2009","unstructured":"Dumitrescu, A., T\u00f3th, C.D.: Light orthogonal networks with constant geometric dilation. J. Discrete Algorithms 7, 112\u2013129 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9329_CR14","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00453-005-1203-9","volume":"44","author":"A. Ebbers-Baumann","year":"2006","unstructured":"Ebbers-Baumann, A., Gr\u00fcne, A., Klein, R.: On the geometric dilation of finite point sets. Algorithmica 44, 137\u2013149 (2006)","journal-title":"Algorithmica"},{"key":"9329_CR15","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02574002","volume":"11","author":"D. Eppstein","year":"1994","unstructured":"Eppstein, D.: Approximating the minimum weight Steiner triangulation. Discrete Comput. Geom. 11, 163\u2013191 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9329_CR16","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. 425\u2013461. Elsevier, Amsterdam (2000)"},{"issue":"1","key":"9329_CR17","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1109\/JSAC.2004.837364","volume":"23","author":"J. Gao","year":"2005","unstructured":"Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanners for routing in mobile networks. IEEE J. Sel. Areas Commun. 23(1), 174\u2013185 (2005)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"9329_CR18","unstructured":"Garc\u00eda-L\u00f3pez, J., Nicol\u00e1s, C.M.: Planar point sets with large minimum convex partitions. In: Proc. of European Workshop on Comput. Geom., pp. 51\u201354, Delphi (2006)."},{"key":"9329_CR19","unstructured":"Gilbert, P.D.: New results in planar triangulations. Report R-850, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois (1979)"},{"issue":"1","key":"9329_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E.N. Gilbert","year":"1968","unstructured":"Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1\u201329 (1968)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"9329_CR21","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.comgeo.2007.05.004","volume":"38","author":"J. Gudmundsson","year":"2007","unstructured":"Gudmundsson, J., Levcopoulos, C.: Minimum weight pseudo-triangulations. Comput. Geom. Theory Appl. 38(3), 139\u2013153 (2007)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9329_CR22","doi-asserted-by":"crossref","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 that approximate the complete Euclidean graph. Discrete Comput. Geom. 7, 13\u201328 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9329_CR23","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1142\/S0218195902000803","volume":"12","author":"J.M. Keil","year":"2002","unstructured":"Keil, J.M., Snoeyink, J.: On the time bound for convex decomposition of simple polygons. Int. J. Comput. Geom. Appl. 12, 181\u2013192 (2002)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9329_CR24","unstructured":"Kim, Y.-J., Govindan, R., Karp, B., Shenker, S.: Geographic routing made practical. In: Proc. of the 2nd Sympos. on Networked Systems Design and Implementation, pp. 217\u2013230, USENIX Assoc. (2005)"},{"issue":"3","key":"9329_CR25","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(80)90062-9","volume":"10","author":"D.G. Kirkpatrick","year":"1980","unstructured":"Kirkpatrick, D.G.: A note on Delaunay and optimal triangulations. Inf. Proc. Lett. 10(3), 127\u2013128 (1980)","journal-title":"Inf. Proc. Lett."},{"key":"9329_CR26","series-title":"Annals of Discrete Math.","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0167-5060(08)70044-X","volume-title":"Submodular Functions and Optimization","author":"G.T. Klincsek","year":"1980","unstructured":"Klincsek, G.T.: Minimal triangulations of polygonal domains. In: Submodular Functions and Optimization. Annals of Discrete Math., vol. 9, pp. 121\u2013123. Elsevier, Amsterdam (1980)"},{"key":"9329_CR27","series-title":"LNCS","first-page":"232","volume-title":"Proc. of the 10th Scandinavian Workshop on Algorithm Theory","author":"C. Knauer","year":"2006","unstructured":"Knauer, C., Spillner, A.: Approximation algorithms for the minimum convex partition problem. In: Proc. of the 10th Scandinavian Workshop on Algorithm Theory. LNCS, vol. 4059, pp. 232\u2013241. Springer, Berlin (2006)"},{"key":"9329_CR28","unstructured":"Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. of the 11th Canadian Conf. on Comput. Geom., pp. 51\u201354, Vancouver, BC (1999)"},{"key":"9329_CR29","first-page":"337","volume-title":"Proc. of the 49th Sympos. on Foundations of Comput. Sci.","author":"T. Leighton","year":"2008","unstructured":"Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. In: Proc. of the 49th Sympos. on Foundations of Comput. Sci., pp. 337\u2013346. IEEE, New York (2008)"},{"issue":"2","key":"9329_CR30","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1006\/jagm.1997.0918","volume":"27","author":"C. Levcopoulos","year":"1998","unstructured":"Levcopoulos, C., Krznaric, D.: Quasi-greedy triangulations approximating the minimum weight triangulation. J. Algorithms 27(2), 303\u2013338 (1998)","journal-title":"J. Algorithms"},{"key":"9329_CR31","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/3-540-13883-8_78","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"C. Levcopoulos","year":"1984","unstructured":"Levcopoulos, C., Lingas, A.: Bounds on the length of convex partitions of polygons. In: Foundations of Software Technology and Theoretical Computer Science. LNCS, vol. 181, pp. 279\u2013295. Springer, Berlin (1984)"},{"key":"9329_CR32","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01758846","volume":"8","author":"C. Levcopoulos","year":"1992","unstructured":"Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8, 251\u2013256 (1992)","journal-title":"Algorithmica"},{"key":"9329_CR33","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BFb0012784","volume-title":"Proc. of the 9th Internat. Colloq. on Automata, Languages and Programming","author":"A. Lingas","year":"1982","unstructured":"Lingas, A.: The power of non-rectilinear holes. In: Proc. of the 9th Internat. Colloq. on Automata, Languages and Programming. LNCS, vol. 140, pp. 369\u2013383. Springer, Berlin (1982)"},{"key":"9329_CR34","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"key":"9329_CR35","doi-asserted-by":"crossref","unstructured":"Mulzer, W., Rote, G.: Minimum weight triangulation is NP-hard. J. ACM 55(2) (2008), article 11","DOI":"10.1145\/1346330.1346336"},{"key":"9329_CR36","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)"},{"issue":"2","key":"9329_CR37","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s00373-004-0555-2","volume":"20","author":"V. Neumann-Lara","year":"2004","unstructured":"Neumann-Lara, V., Rivera-Campo, E., Urrutia, J.: A note on convex decompositions of a set of points in the plane. Graphs Comb. 20(2), 223\u2013231 (2004)","journal-title":"Graphs Comb."},{"key":"9329_CR38","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2005.06.022","volume":"344","author":"C.H. Papadimitriou","year":"2005","unstructured":"Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theor. Comput. Sci. 344, 3\u201314 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9329_CR39","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/0196-6774(87)90020-4","volume":"8","author":"D.A. Plaisted","year":"1987","unstructured":"Plaisted, D.A., Hong, J.: A heuristic triangulation algorithm. J. Algorithms 8(3), 405\u2013437 (1987)","journal-title":"J. Algorithms"},{"key":"9329_CR40","first-page":"96","volume-title":"Proc. of the 9th Conf. on Mobile Computing and Networking","author":"A. Rao","year":"2003","unstructured":"Rao, A., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location information. In: Proc. of the 9th Conf. on Mobile Computing and Networking, pp. 96\u2013108. ACM, New York (2003)"},{"key":"9329_CR41","first-page":"316","volume-title":"Proc. of the 38th Sympos. on Theory of Computing","author":"J. Remy","year":"2006","unstructured":"Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. In: Proc. of the 38th Sympos. on Theory of Computing, pp. 316\u2013325. ACM, New York (2006) (to appear in J. ACM)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9329-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9329-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9329-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:04Z","timestamp":1559123104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9329-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,12]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["9329"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9329-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,12]]}}}