Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

CGGC Seminar: Algorithms for Heilbronn's triangle problem
event speaker icon
Osnat Tal (Computer Science, Technion)
event date icon
Sunday, 18.01.2009, 13:00
event location icon
Room 337-8 Taub Bld.
The classic Heilbronn's triangle problem is to maximize the area of the smallest of the $\binom{n}{3}$ triangles determined by $n$ points in the unit square. One aspect of the problem is finding the optimal locations of the points. Another issue is finding lower and upper bounds on the smallest triangle's area in the optimal configuration(s) of points. With respect to the first aspect, mathematicians and computer scientists have worked in the last decades to find good configurations for various numbers of points. Some of the best-known configurations have not been improved upon for decades, and others were only improved upon in the last few years. In most cases, it is unknown if these configurations are optimal or if they can be improved upon, since a proof of optimality is missing.

In this work we present algorithms and heuristics which we used in order to find high-value configurations. First, we show some characteristics of Heilbronn configurations. We then present the main tool we used, a grid search, in order to find ``quite good'' configurations. In order to make the search feasible on the grid, it was imperative to make some substantial efficiency improvements. We also looked for configurations with a large number of points, beyond the capability of the grid search. For these, we implemented a confinguration editor, with which we obtained good initial results. The configurations found so far were improved by a simulated-annealing heuristic. In the final step we attempted to analytically improve upon these configurations by solving a system of equations and constraints that represented minimal triangles defined over the specific point set. In addition, we present a method which we initially used, whose results were worse than what we expected. We analyze the method and show why it did not meet our expectations.

This talk summarizes the M.Sc. research of the speaker under the supervision of Prof. Gill Barequet.