A Two-Phase Heuristic Search Approach to the Heilbronn Triangle Problem for n = 10, 11, 12

Abstract

The Heilbronn triangle problem asks how to place n points in a unit square so that the minimum area triangle formed by any three of them is as large as possible. For n beyond roughly nine points, no configuration has been proven optimal, and progress has relied on a mix of analytical construction and computational search. This paper describes a two-phase heuristic search — simulated annealing followed by multi-candidate hill-climbing and basin hopping — applied to n = 10, 11, and 12, with results benchmarked directly against the best-known published values. Across three independent repeats per value of n, the method reached within 0.6% of the best-known configuration for n = 10 and within 2.0% for n = 11, while n = 12 showed a persistent 14-16% gap. We report the full distribution of results, not just best-case figures, and use the observed run-to-run variance and the widening gap at n = 12 to discuss how search difficulty scales with problem size for this class of geometric optimization problem.