WikiDer > Проблема треугольника Хейльбронна

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

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

Определение

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

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

.

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

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

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

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

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

[2]

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

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

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

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

Определенные формы и числа

Гольдберг (1972) исследовал оптимальное расположение п точки в квадрате, для п до 16.[4] Построения Гольдберга для шести точек лежат на границе квадрата и размещаются так, чтобы образовать аффинное преобразование вершин правильный многоугольник. Для больших значений п, Комели и Йебра (2002) улучшены оценки Голдберга, и для этих значений решения включают точки, лежащие внутри квадрата.[5] Эти конструкции были признаны оптимальными по семи точкам.[6]

Вариации

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

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

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

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

  1. ^ а б Рот, К.Ф. (1951), «О проблеме Хайльбронна», Журнал Лондонского математического общества, 26 (3): 198–204, Дои:10.1112 / jlms / s1-26.3.198.
  2. ^ Комлос, Я.; Пинц, Дж.; Семереди, Э. (1982), "Нижняя оценка проблемы Хейльбронна", Журнал Лондонского математического общества, 25 (1): 13–24, Дои:10.1112 / jlms / s2-25.1.13, Г-Н 0645860.
  3. ^ Комлос, Я.; Пинц, Дж.; Семереди, Э. (1981), "О проблеме треугольника Хейльбронна", Журнал Лондонского математического общества, 24 (3): 385–396, Дои:10.1112 / jlms / с2-24.3.385, Г-Н 0635870.
  4. ^ Голдберг, Майкл (1972), "Максимизация наименьшего треугольника, сделанного п точки в квадрате », Математический журнал, 45: 135–144, Дои:10.2307/2687869, JSTOR 2687869, Г-Н 0296816.
  5. ^ Comellas, Francesc; Йебра, Дж. Луис А. (2002), «Новые нижние границы для чисел Хейльбронна», Электронный журнал комбинаторики, 9 (1): R6, Г-Н 1887087.
  6. ^ Цзэн, Чжэньбинь; Чен, Лянъюй (2011), "Об оптимальной конфигурации семи точек в квадрате Хейльбронна", Автоматический вывод по геометрии, Конспект лекций по вычисл. Наук, 6301, Heidelberg: Springer, стр. 196–224, Дои:10.1007/978-3-642-21046-4_11, Г-Н 2805061.
  7. ^ Цзян, Дао; Ли, Мин; Витани, Пол (2002), "Средняя площадь треугольников типа Хейльбронна", Случайные структуры и алгоритмы, 20 (2): 206–219, arXiv:математика / 9902043, Дои:10.1002 / rsa.10024, Г-Н 1884433.
  8. ^ Гримметт, Г.; Янсон, С. (2003), «О самых маленьких треугольниках», Случайные структуры и алгоритмы, 23: 206–223.
  9. ^ Лефманн, Ханно (2008), "Распределение точек в d размеры и большие k-точечные симплексы », Дискретная и вычислительная геометрия, 40 (3): 401–413, Дои:10.1007 / s00454-007-9041-y, Г-Н 2443292.

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