Задача Хайльбронна: 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).
  1. 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...

  2. tejstead

    Привет,

    Я сделал этот сайт, чтобы показать задачу Хайльбронна — классическую задачу оптимизации. В последнее время наблюдается волна вкладов новых рекордов от математиков-любителей — вы могли бы стать одним из них!

  3. dataflow

    Каков критерий для включения в список текущего лучшего известного значения? (Я немного запутался, почему этот список не бесконечно длинный.)

Ещё за этот день

2026-10-04