Задача Хайльбронна: Rob Gardiner побил рекорды для квадрата и треугольника
The Heilbronn Problem
Сайт собирает лучшие известные конфигурации для задачи Хайльбронна — размещения n точек в области единичной площади так, чтобы наименьший треугольник из любых трёх точек имел максимально возможную площадь. Для квадрата, треугольника и выпуклых областей приведены точные координаты, анализ симметрии, ссылки на доказательства и онлайн-верификатор на рациональной арифметике. В последних записях Rob Gardiner улучшил результаты для квадрата (n=21, 23, 25, 35) и треугольника (n=20), а Alexandar Lackovic с помощью Opus 5.5 — для выпуклых областей (n=31, 33).
Разместите n точек в области единичной площади так, чтобы наименьший треугольник, определяемый любыми тремя точками, имел наибольшую возможную площадь A(n).
- arutar
Круто видеть на HN кусок математики, который мне лично очень интересен!
С точки зрения чистой математики меня больше всего интересует асимптотика (что происходит, когда n становится очень большим).
Несколько фактов, которые могут быть интересны:
* Вот аргумент, показывающий, что всегда должен существовать треугольник площадью меньше примерно 1/n. Разделите единичный квадрат на n/3 вертикальных полос. По принципу Дирихле в одной из полос должно оказаться три точки. Площадь полосы примерно 1/n, значит, и площадь треугольника не больше 1/n.
* Напротив, лучшая известная нижняя оценка — что-то вроде (log n)/n^2 — очень далеко от 1/n.
* После довольно большой работы ряда авторов Комлош, Пинтц и Семереди в 1981 году доказали верхнюю оценку по существу вида n^(-8/7), всё ещё довольно далёкую от нижней оценки n^2!
* Примечательно, что прогресса не было более 40 лет, пока несколько лет назад два аспиранта MIT (Alex Cohen и Dima Zakharov) вместе с Cosmin Pohoata не побили эту верхнюю оценку на некоторый небольшой множитель, а затем ещё через год или около того улучшили её до n^(-7/6). (См. [1] для обзора их работы.)
* Эта задача связана с более общим семейством задач геометрии инцидентности, называемых «нижние оценки для инциденций»: дана некоторая коллекция геометрических объектов (скажем, точки и прямые), при каких условиях мы можем гарантировать, что на самом деле «почти инциденций» больше, чем мы изначально ожидали?
[1] https://www.quantamagazine.org/the-biggest-smallest-triangle...
- tejstead
Привет,
Я сделал этот сайт, чтобы показать задачу Хайльбронна — классическую задачу оптимизации. В последнее время наблюдается волна вкладов новых рекордов от математиков-любителей — вы могли бы стать одним из них!
- dataflow
Каков критерий для включения в список текущего лучшего известного значения? (Я немного запутался, почему этот список не бесконечно длинный.)