Задача треугольника Хейльбронна - Heilbronn triangle problem

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

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

Определение

Проблема может быть определена в терминах любой компактной множества D в плоскости с ненулевой области , такие как единичного квадрата или единичного круга . Если S - набор из n точек D , то каждые три точки S определяют треугольник (возможно, вырожденный, с нулевой площадью). Пусть Δ ( S ) обозначает минимум площадей этих треугольников, а Δ ( n ) (для целого числа n  ≥ 3) обозначает верхнюю грань значений Δ ( S ).

Вопрос, поставленный Хейльбронном, состоял в том, чтобы дать выражение или согласовать асимптотические верхние и нижние границы для Δ ( n ). То есть цель состоит в том, чтобы найти функцию f , описываемую выражением в замкнутой форме , и константы c ₁ и c ₂ , такие, что для всех n ,

${\ Displaystyle c_ {1} е (п) \ leq \ Delta (п) \ leq c_ {2} е (п)}$.

В терминах большой записи O левое неравенство можно записать как Δ ( n ) = Ω ( f ( n )), правое неравенство можно записать как Δ ( n ) =  O ( f ( n )), и оба их вместе можно записать как Δ ( n ) = Θ ( f ( n )). Форма и площадь D могут влиять на точные значения Δ ( n ), но только с постоянным множителем, поэтому они не важны для его асимптотической скорости роста.

Гипотеза Хейльбронна и конструкции нижних оценок

Хейльбронн предположил, что

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

Как показал Пол Эрдеш , меньшая граница невозможна: когда n - простое число , набор из n точек ( i ,  i ²  mod  n ) на целочисленной сетке n  ×  n не имеет трех коллинеарных точек , и, следовательно, по формуле Пика каждая из треугольников, которые они образуют, имеет площадь не менее 1/2. Когда этот набор узлов сетки масштабируется до единичного квадрата, они образуют набор точек, наименьшая площадь треугольника которых, по крайней мере, пропорциональна 1 / n ² , что соответствует предполагаемой верхней границе Хейльбронна. Если n не является простым, то аналогичная конструкция с использованием следующего простого числа, большего, чем n, достигает той же асимптотической нижней границы.

Komlós, Pintz & Szemerédi (1982) в конце концов опровергли гипотезу Хейльбронна, найдя наборы точек, наименьшая площадь треугольника которых растет асимптотически при

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

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

Тривиально, либо триангуляции на выпуклую оболочку данного множества точек S или выбрав последовательных троек точек в отсортированном порядке их х -координаты, можно показать , что каждая точка множества содержит небольшой треугольник, площадь которого составляет не более обратно пропорционально  n . Рот (1951) был первым, кто доказал нетривиальную оценку сверху Δ ( n ) вида

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

Лучшая связка, известная на сегодняшний день, имеет форму

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

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

Особые формы и числа

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

Вариации

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

Смотрите также

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

использованная литература

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

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