אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.