caa a22 4500 445804394 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-009-9329-9 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9329-9 Minimum Weight Convex Steiner Partitions [Elektronische Daten] [Adrian Dumitrescu, Csaba Tóth] New tight bounds are presented on the minimum length of planar straight line graphs connecting n given points in the plane and having convex faces. Specifically, we show that the minimum length of a convex Steiner partition for n points in the plane is at most O(log n/log log n) times longer than a Euclidean minimum spanning tree (EMST), and this bound is the best possible. Without Steiner points, the corresponding bound is known to be Θ(log n), attained for n vertices of a pseudo-triangle. We also show that the minimum length convex Steiner partition of n points along a pseudo-triangle is at most O(log log n) times longer than an EMST, and this bound is also the best possible. Our methods are constructive and lead to O(nlog n) time algorithms for computing convex Steiner partitions having O(n) Steiner points and weight within the above worst-case bounds in both cases. Springer Science+Business Media, LLC, 2009 Convex partition nationallicence Network design nationallicence Stretch factor nationallicence Steiner points nationallicence Dumitrescu Adrian Department of Computer Science, University of Wisconsin-Milwaukee, 53201-0784, Milwaukee, WI, USA aut Tóth Csaba Department of Mathematics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada aut Algorithmica Springer-Verlag 60/3(2011-07-01), 627-652 0178-4617 60:3<627 2011 60 453 https://doi.org/10.1007/s00453-009-9329-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9329-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dumitrescu Adrian Department of Computer Science, University of Wisconsin-Milwaukee, 53201-0784, Milwaukee, WI, USA aut NATIONALLICENCE 700 1- Tóth Csaba Department of Mathematics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 627-652 0178-4617 60:3<627 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer