Задача хайльброннского треугольника

Нерешенная задача по математике :

Какова асимптотическая скорость роста площади наименьшего треугольника, определяемого тремя из $n$ точки в квадрате, когда точки выбираются так, чтобы максимизировать эту площадь?

(еще нерешенные задачи по математике)

Шесть точек в единичном квадрате, причем наименьшие треугольники (красные) имеют площадь 1/8, оптимальную площадь для такого количества точек. Другие треугольники большего размера окрашены в синий цвет. Эти точки представляют собой аффинное преобразование правильного шестиугольника , но для большего числа точек оптимальное решение не образует выпуклый многоугольник.

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

Определение

Задача хайльброннского треугольника касается размещения $n$ точки внутри фигуры на плоскости, например единичный квадрат или единичный диск , для заданного числа $n$. Каждая тройка точек образует три вершины треугольника , и среди этих треугольников задача касается самого маленького треугольника, измеренного по площади. Разное расположение точек будет иметь разные наименьшие треугольники, и возникает вопрос: как следует $n$ точки расположить так, чтобы максимизировать площадь наименьшего треугольника?

Более формально можно предположить, что форма представляет собой компактное множество. $D$ на плоскости, что означает, что он остается на ограниченном расстоянии от начала координат и что на его границе разрешено размещать точки. В большинстве работ по этой проблеме $D$ дополнительно является выпуклым множеством ненулевой площади. Когда три из размещенных точек лежат на прямой , они считаются образующими вырожденный треугольник, площадь которого определяется как ноль, поэтому места размещения, которые максимизируют наименьший треугольник, не будут иметь коллинеарные тройки точек. Предположение о компактности формы подразумевает, что существует оптимальное размещение $n$ очков, а не просто последовательность размещений, приближающихся к оптимальности. Число $\Delta _{D}(n)$ может быть определена как площадь наименьшего треугольника в этом оптимальном расположении. Пример показан на рисунке с шестью точками в единичном квадрате. Эти шесть пунктов образуют ${\tbinom {6}{3}}=20$ разные треугольники, четыре из которых на рисунке заштрихованы. Шесть из этих 20 треугольников, две из которых заштрихованы, имеют площадь 1/8; остальные 14 треугольников имеют большую площадь. Это оптимальное размещение шести точек в единичном квадрате: все остальные размещения образуют как минимум один треугольник площадью 1/8 или меньше. Поэтому, $\Delta _{D}(6)={\tfrac {1}{8}}$.

Хотя исследователи изучили ценность $\Delta _{D}(n)$ для определенных форм и определенного небольшого количества точек, Вместо этого Хейльбронна беспокоило ее асимптотическое поведение : если форма $D$ остается фиксированным, но $n$ меняется, как меняется площадь наименьшего треугольника в зависимости от $n$? То есть вопрос Хайльбронна касается темпов роста $\Delta _{D}(n)$, функция как $n$. Для любых двух фигур $D$ и $D'$, числа $\Delta _{D}(n)$ и $\Delta _{D'}(n)$ различаются только постоянным коэффициентом, так как любое размещение $n$ точки внутри $D$ может быть масштабирован с помощью аффинного преобразования, чтобы соответствовать $D'$, изменяя минимальную площадь треугольника только на константу. Поэтому в границах темпа роста $\Delta _{D}(n)$ которые опускают константу пропорциональности этого роста, выбор $D$ не имеет значения, и нижний индекс может быть опущен.

Хейльбронна и

До 1951 года Хейльбронн предположил, что минимальная площадь треугольника всегда быстро сжимается в зависимости от $n$— точнее, обратно пропорционально квадрату $n$. В терминах обозначения большого О это можно выразить как границу

$$\Delta (n)=O\left({\frac {1}{n^{2}}}\right).$$

Решения проблемы отсутствия трех рядов : большие наборы точек сетки без трех коллинеарных точек могут быть масштабированы до единичного квадрата с минимальной площадью треугольника. $\Omega (1/n^{2})$.

В другом направлении Пол Эрдеш нашел примеры наборов точек с минимальной площадью треугольника, пропорциональной $1/n^{2}$, демонстрируя, что, если это правда, предполагаемую границу Хейльбронна нельзя усилить. Чтобы описать эти примеры, Эрдеш сформулировал проблему отсутствия трех строк для больших наборов точек сетки, в которых нет трех строк. Как заметил Эрдеш, когда $n$ — простое число , множество $n$ очки $(i,i^{2}{\bmod {n}})$ на $n\times n$ целочисленная сетка (для $0\leq i<n$) не имеют трех коллинеарных точек, и поэтому по формуле Пика каждый из образуемых ими треугольников имеет площадь не менее ${\tfrac {1}{2}}$. Когда эти точки сетки масштабируются так, чтобы они помещались в пределах единичного квадрата, их наименьшая площадь треугольника пропорциональна $1/n^{2}$, что соответствует предполагаемой верхней границе Хейльбронна. Если $n$ не является простым, то аналогичная конструкция с использованием простого числа, близкого к $n$ достигает той же асимптотической нижней границы.

Комлос, Пинц и Семереди (1982) в конечном итоге опровергли гипотезу Хейльбронна, используя вероятностный метод для поиска наборов точек, наименьшая площадь треугольника которых больше, чем у Эрдеша. Их строительство включает в себя следующие этапы:

• Случайное место $n^{1+\varepsilon }$ точки в единичном квадрате, для некоторых $\varepsilon >0$.
• Удалите все пары точек, которые неожиданно оказались близко друг к другу.
• Докажите, что осталось мало треугольников с малой площадью и, следовательно, только сублинейное количество циклов, образованных двумя, тремя или четырьмя треугольниками с малой площадью. Удалите все точки, принадлежащие этим циклам.
• Примените лемму об удалении треугольников для 3-однородных гиперграфов большого обхвата , чтобы показать, что с высокой вероятностью оставшиеся точки включают подмножество $n$ точки, которые не образуют треугольников малой площади.

Площадь, образующаяся в результате их построения, растет асимптотически по мере

$$\Delta (n)=\Omega \left({\frac {\log n}{n^{2}}}\right).$$

Доказательство можно дерандомизировать , что приведет к полиномиальному алгоритму построения мест размещения с этой треугольной областью.

Верхние границы

Каждый набор $n$ точки единичного квадрата образуют треугольник, площадь которого не более чем обратно пропорциональна $n$. Один из способов убедиться в этом — триангулировать выпуклую оболочку заданного набора точек. $S$и выберите наименьший из треугольников триангуляции. Другой способ — отсортировать точки по их $x$-координаты и выбрать три последовательные точки в этом порядке, чьи $x$-координаты максимально близки друг к другу. В первой статье, опубликованной по проблеме треугольника Гейльбронна в 1951 году, Клаус Рот доказал более сильную верхнюю оценку для $\Delta (n)$, формы

$$\Delta (n)=O\left({\frac {1}{n{\sqrt {\log \log n}}}}\right).$$

Наилучшая известная на сегодняшний день граница имеет вид

$$\Delta (n)\leq {\frac {\exp {\left(c{\sqrt {\log n}}\right)}}{n^{8/7}}},$$

для некоторой константы $c$, доказано Комлосом, Пинцем и Семереди (1981) .

Новая верхняя граница, равная $n^{-{\frac {8}{7}}-{\frac {1}{2000}}}$ было доказано Коэном, Похоатой и Захаровым (2023) .

Конкретные формы и цифры

Голдберг (1972) исследовал оптимальные схемы $n$ точки в квадрате, для $n$ до 16. Конструкции Гольдберга для числа до шести точек лежат на границе квадрата и размещаются так, чтобы образовать аффинное преобразование вершин правильного многоугольника . Для больших значений $n$, Комеллас и Йебра (2002) улучшили границы Гольдберга, и для этих значений решения включают точки внутри квадрата. Эти конструкции оказались оптимальными по семи точкам. В доказательстве использовался компьютерный поиск для разделения конфигурационного пространства возможных расположений точек на 226 различных подзадач, а также использовались методы нелинейного программирования, чтобы показать, что в 225 из этих случаев наилучшее расположение не так хорошо, как известная граница. В оставшемся случае, включая окончательное оптимальное решение, его оптимальность была доказана с использованием методов символьных вычислений .

Ниже приведены наиболее известные решения для 7–12 точек на единичном квадрате, найденные с помощью моделирования отжига ; Расстановка по семи пунктам, как известно, оптимальна.

• 
  7 точек в квадрате, все 8 минимальных треугольников заштрихованы ( $A\approx 0.0839$)
• 
  8 точек в квадрате, 5 из 12 минимальных треугольников заштрихованы. ( $A\approx 0.0724$)
• 
  9 точек в квадрате, 6 из 11 минимальных треугольников заштрихованы. ( $A\approx 0.0549$)
• 
  10 точек в квадрате, 3 из 16 минимальных треугольников заштрихованы. ( $A\approx 0.0465$)
• 
  11 точек в квадрате, 8 из 28 минимальных треугольников заштрихованы. ( $A\approx 0.0370$)
• 
  12 точек в квадрате, 3 из 20 минимальных треугольников заштрихованы. ( $A\approx 0.0326$)

Вместо поиска оптимального размещения для данной фигуры можно искать оптимальную форму для заданного количества точек. Среди выпуклых форм $D$ с площадью один правильный шестиугольник - это тот, который максимизирует $\Delta _{D}(6)$; для этой формы, $\Delta _{D}(6)={\tfrac {1}{6}}$, с шестью точками, оптимально расположенными в вершинах шестиугольника. Выпуклые формы единичной площади, которые максимизируют $\Delta _{D}(7)$ иметь $\Delta _{D}(7)={\tfrac {1}{9}}$.

Вариации

Было много вариантов этой проблемы включая случай равномерно случайного набора точек, для которого аргументы, основанные либо на колмогоровской сложности , либо на пуассоновском приближении, показывают, что ожидаемое значение минимальной площади обратно пропорционально кубу количества точек. вариации, связанные с объемом симплексов более высокой размерности. Также были изучены

Вместо рассмотрения симплексов в другой многомерной версии добавляется еще один параметр. $k$и запрашивает размещение $n$ точки единичного гиперкуба , которые максимизируют минимальный объем выпуклой оболочки любого подмножества $k$ точки. Для $k=d+1$ эти подмножества образуют симплексы, но для больших значений $k$, относительно ​ $d$, они могут образовывать более сложные формы. Когда $k$ достаточно велика по отношению к $\log n$, случайно расположенные множества точек имеют минимум $k$-точечный выпуклой оболочки объем $\Omega (k/n)$. Лучшей границы быть не может; любое размещение имеет $k$ точки с объемом $O(k/n)$, полученный выбором некоторого $k$ последовательные точки в координатном порядке. Этот результат имеет применение в структурах данных поиска по диапазону .

См. также

• Набор Данцера — набор точек, позволяющий избежать пустых треугольников большой площади.

Внешние ссылки

• Вайсштейн, Эрик В. , «Задача Хайльброннского треугольника» , MathWorld
• Центр упаковки Эриха Эриха Фридмана, включая наиболее известные решения проблемы Гейльбронна для малых значений $n$ для квадратов, кругов, равносторонних треугольников и выпуклых областей переменной формы, но фиксированной площади