The Taub Faculty of Computer Science Events and Talks

Heilbronn's triangle problem asks how to place n points in the unit square, such that the smallest of the $\binom{n]{ 3}$ triangles is maximized. This problem, which was opened in the 1950s by the mathematician Heilbronn, has not yet been answered for n>8. Calling H)n( the area of the smallest triangle of the best set of n points, no tight bounds on it have been found so far. The best upper and lower bounds are $O(n^{-\mu+\epsilon})$, where $\mu=\frac{8}{7}$ , and $\Omega(\frac{\log n}{n^2})$ respectively, which still leaves a large gap. Heilbronn's triangle problem has many variants, for example, reducing the set of possible point sets to those where some properties hold. On the other hand, finding a 'good' solution to Heilbronn's problem has been attempted algorithmically up to only 24 points since the complexity of the algorithms used making them non-applicable for large number of points. In fact, not much has been found about the structure of the best point sets, such as the number of smallest triangles, the number of points lying on the boundary of the unit square, etc. In this talk, we investigate the location of points in locally-optimum configurations of points, as well as some properties that should hold for optimal point sets. From those properties, we also derive other properties for variants of Heilbronn's triangle problem, in which the point are in monotone-decreasing position or convex-decreasing position. Finally, we use a particle swamp algorithm variation in order to find a solution as good as possible for $n>24$, thus, reducing time complexity and being as close as possible to the best known point sets for $n\leq 24$.