Technical Report MSC-2009-08

TR#:MSC-2009-08
Class:MSC
Title: Algorithms for Heilbronn's Triangle Problem
Authors: Asenath Tal
Supervisors: Assoc. Prof. Gill Barequet
PDFMSC-2009-08.pdf
Abstract: 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 highvalue 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2009/MSC/MSC-2009-08), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2009
To the main CS technical reports page

Computer science department, Technion
admin