Введение

В дискретной геометрии и теории расхождений проблема Гейльбронна — это задача о размещении точек на плоскости так, чтобы избежать треугольников с малой площадью. Она названа в честь Ганса Гейльбронна, который предположил, что независимо от способа размещения точек в заданной области, минимальная площадь треугольника будет не больше величины, обратно пропорциональной квадрату числа точек. Его предположение было опровергнуто, но асимптотическая скорость роста минимальной площади треугольника остаётся неизвестной.

Определение

Проблема треугольника Гейльбронна касается размещения точек внутри фигуры на плоскости, такой как единичный квадрат или единичный диск, для заданного числа. Каждая тройка точек образует три вершины треугольника, и среди этих треугольников проблема заключается в поиске треугольника с наименьшей площадью. Различные размещения точек приводят к разным треугольникам с наименьшей площадью, и задача состоит в том, чтобы определить, как следует размещать точки, чтобы максимизировать площадь наименьшего треугольника. Формально, фигуру можно рассматривать как компактное множество на плоскости, что означает, что она остается в пределах ограниченного расстояния от начала координат и что точки могут быть размещены на ее границе. В большинстве работ по этой проблеме фигура дополнительно является выпуклым множеством ненулевой площади. Если три из размещенных точек лежат на одной прямой, они рассматриваются как образующие вырожденный треугольник, площадь которого определяется как ноль, поэтому размещения, максимизирующие наименьший треугольник, не будут содержать коллинеарных троек точек. Предположение о компактности фигуры подразумевает, что существует оптимальное размещение точек, а не только последовательность размещений, приближающихся к оптимальному. Число можно определить как площадь наименьшего треугольника в этом оптимальном размещении. Пример показан на рисунке, с шестью точками в единичном квадрате. Эти шесть точек образуют различных треугольников, четыре из которых затенены на рисунке. Шесть из этих 20 треугольников, включая два затененных, имеют площадь 1/8; остальные 14 треугольников имеют большую площадь. Это оптимальное размещение шести точек в единичном квадрате: любое другое размещение образует по крайней мере один треугольник площадью 1/8 или меньше. Поэтому, хотя исследователи изучали значение для конкретных фигур и небольшого числа точек, Гейльбронна больше интересовало его асимптотическое поведение: если фигура фиксирована, но изменяется, как изменяется площадь наименьшего треугольника с ростом ? То есть, вопрос Гейльбронна касается скорости роста как функции от . Для любых двух фигур и числа и отличаются только постоянным множителем, поскольку любое размещение точек внутри можно масштабировать аффинным преобразованием, чтобы оно поместилось внутри , изменяя минимальную площадь треугольника только на постоянную величину. Поэтому, в оценках скорости роста , не учитывающих постоянную пропорциональность этого роста, выбор не имеет значения, и индекс можно опустить.

Особые формы и цифры

Исследовала оптимальное расположение точек в квадрате для значений до 16. Конструкции Гольдберга для шести и менее точек лежат на границе квадрата и расположены таким образом, что образуют аффинное преобразование вершин правильного многоугольника. Для больших значений , границы Гольдберга были улучшены, и для этих значений решения включают точки, находящиеся внутри квадрата. Эти конструкции были доказаны как оптимальные для семи и менее точек. В доказательстве использовался компьютерный поиск для разбиения пространства конфигураций возможных расположений точек на 226 различных подзадач, и применялись методы нелинейного программирования, чтобы показать, что в 225 из этих случаев наилучшее расположение не превосходило известную границу. В оставшемся случае, включая окончательное оптимальное решение, его оптимальность была доказана с использованием методов символьных вычислений. Ниже приведены наилучшие известные решения для 7–12 точек в единичном квадрате, полученные методом имитации отжига; расположение для семи точек известно как оптимальное. Вместо поиска оптимальных положений для заданной формы можно искать оптимальную форму для заданного числа точек. Среди выпуклых фигур с площадью, равной единице, правильный шестиугольник максимизирует ; для этой фигуры, , при оптимальном расположении шести точек в вершинах шестиугольника. Выпуклые фигуры единичной площади, максимизирующие , имеют