A New Upper Estimate for the Fermat-Torricelli Ratio

Overview

Given P, a set of clients (points) in the plane, the task is to open a facility and connect each client to this facility while minimizing the connecting cost. If one assumes that this cost is proportional to the total length of the connecting segments, then the optimal location for the facility is known as the Fermat - Torricelli center of the initial set of points, P. I study the following single facility location problem which was proposed in 2000 by Fekete and Meijer: How much worse than the optimal solution can a solution be if the facility must be opened at one of the clients' locations? In mathematical terms, the problem is asking for an estimate of alpha(P), the quotient between the length of the shortest rooted star and the length of the Fermat - Torricelli star of the given set. In this paper, I improve a series of three prior estimates and prove that alpha(P) can never exceed 1.3385. My main idea is to consider P', the reflection of P across the Fermat-Torricelli center of P. I also introduce a new function, gamma(P) =2D(P)/|P|, which is an overestimate for alpha(P), where D(P) denotes the sum of the distances among points in P and |P| is the cardinality of the set P. I use a result of Morgenstern to prove that gamma(P) is never larger than gamma(P union P') and then I exploit the central symmetry of the combined set P union P' to derive an improved upper estimate for D(P union P'), the sum of all distances determined by pairs of points in P union P'. The final estimate follows from the double inequality: alpha(P)<=gamma(P)<=gamma(P union P'). The latter quantity can be shown to be less than 1.3385, thus establishing the desired result.

Awards (3)

• American Mathematical Society: One-Year Membership to American Mathematical Society to each winner (7 winning projects, up to 3 team members per project)
• American Mathematical Society: Third Award of $500 $500
• Mu Alpha Theta, National High School and Two-Year College Mathematics Honor Society: Second Award of $1,000 $1,000

Competition history

• ISEF 2026 Mathematics · Entry MATH027

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.