Booth Id:
MATH041
Category:
Year:
2016
Finalist Names:
Jung, Woosung
Abstract:
Let P={P1,P2,...,Pn} be a set of n points in the plane. For every 1<=i<=n, define the star rooted at Pi as the union of all straight-line segments joining Pi to all the other points in the set P. A Steiner star is the union of all straight-line segments connecting some point in the plane to each point of P. The length of a star is defined as the total Euclidean length of its edges. The point W(P), which is the center of the Steiner star of minimum length, is called the Weber point of point set P.
We consider the problem of estimating the supremum of the ratio between the rooted star of minimal length and the Weber star, the Steiner star of minimal length, taken over all n point configurations in the plane. It is conjectured that this number, known as the Steiner ratio, is 4/pi = 1.2732... Fekete and Meijer proved that this ratio is bounded from above by sqrt(2) = 1.4142... In 2009, Dumitrescu, Toth and Xu proved a better upper bound of 1.3631. By a refinement of their approach, Ismailescu and Park recently improved this estimate to 1.3546.
In this paper we further lower this bound to 4/3 = 1.3333... This follows from a more careful analysis of the sum between the star rooted at the point closest to the Weber point of P on one hand, and the average length of all rooted stars, on the other hand. We reduce the proof to solving a nonconvex quadratic optimization problem, which in turn we prove it is equivalent to showing that two convex optimization programs have a strictly positive optimum.
Our result is of practical significance as many economical decision problems concern selecting or placing certain facilities to meet given demands efficiently. Examples are manufacturing plants, electrical stations, offshore platforms, etc...