M.Sc Student | Tal Asenath |
---|---|

Subject | Algorithms for Heilbronn's Triangle Problem |

Department | Department of Computer Science |

Supervisor | Professor Gill Barequet |

Full Thesis text |

The classic Heilbronn’s triangle problem is to maximize the area of the smallest of the n!/((n-3)!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, researchers sought good configurations for various numbers of points. Some of the best-known configurations have not been improved for decades, and others were only improved in the last few years. In most cases, it is unknown if these configurations are optimal or if they can be improved, since a proof of optimality is missing.

In this thesis 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 configuration 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.