Проблема Лебега, идеи решения.
Даны 2 треугольника.
Определим функцию S от трёх переменных (сдвиг по x, сдвиг по y, угол поворота φ), которая на выходе даёт площадь выпуклой оболочки этих 2 треугольников с соответствующими x,y,φ.
Задача 1. написать программу, которая проверит численно и ответит: унимодальна S(x,y,φ) или нет?
Определим функцию Lebesgue от 6 переменных, которая получает на вход 2 треугольника, заданных длинами сторон и выдаёт на выходе минимальное возможное S по всем значениям x,y,φ.
Задача 2. Программа получает на вход два треугольника и на выходе выдаёт
- для каждого из возможных компонент связности взаимных расположений треугольников: какой минимум функции S достигается и на каком взаимном расположении?
- из всех этих минимумов: какой самый маленький? (это будет Lebesgue от них).
Программу для п.2 можно писать двумя способами:
2а) численно
2б) выписав в явном виде функцию (для каждой компоненты связности эта функция будет частным двух полиномов) и обработав её аналитически
На первом шаге нужно написать так, как проще.
Задача 3. Попробовать переоткрыть результат Ковалёва: найти минимальную выпуклую покрышку для треугольников диаметра 1.
В зависимости от того, с какой скоростью работает программа из п.2 нужно применять разные способы. Простейший: кидать случайно разные пары треугольников диаметра 1 и смотреть S от этой пары треугольников. Попытаться угадать ответ. Потом для каждой из угаданных гипотез об ответе - пробовать совать в неё другие треугольники диаметра 1.
Задача 4. Попробовать создать новый результат - найти минимальную выпуклую покрышку для всех четырёхугольников диаметра 1. Она существует - но как выглядит, никто не знает.
Справочно.
1) Формула для площади треугольника - многочлен от 6 переменных (координаты x,y трёх вершин)
Для каждой конкретной компоненты связности модуль раскрывается либо в плюс, либо в минус.
2) Формула поворота точки на угол φ вокруг начала координат:
3) Что такое "компонента связности взаимных расположений треугольников".
Прямые, образующие треугольник А, делят плоскость на 7 частей. Каждая из вершин треугольника B может лежать в одной из этих 7 частей. Это даёт 7^3 вариантов.
Аналогично прямые, образующие треугольник B, делят плоскость на 7 частей. Каждая из вершин треугольника A может лежать в одной из этих 7 частей. Это даёт 7^3 вариантов.
Итого теоретически возможны 7^6 вариантов ≈ 100 тысяч.
В реальности почти все из них не реализуются. Проверить, какие реализуются, можно так: весь возможный шаг по x разделить на 100 шажков. Так же по y и по φ. Итого рассмотреть 10^6 возможных картинок. Для каждой из этого миллиона картинок посчитать слепок из 18 плюс-минус единиц - знак площади ориентированного треугольника A1-B1-B2 и аналогичных (одна вершина взята из одного треугольника, две - из другого). Если у двух картинок эти слепки совпадают - они в одной компоненте связности.
Подробнее о проблеме Лебега в целом:
Назовем диаметром многоугольника длину наибольшей его стороны или диагонали. Для проверки понимания: у правильного треугольника с диаметром 1 сторона равна 1. А у квадрата диаметром 1 сторона равна sqrt(2)/2.
Рассмотрим круг с радиусом 1. Можно доказать, что этим кругом можно покрыть любой многоугольник диаметра 1 (докажи!). А можно ли этот круг уменьшить (с сохранением свойства) ? Да. Более сложно, но можно доказать, что и меньший круг, радиуса sqrt(3)/3 также является покрышкой для любого многоугольника диаметра 1. Это в 1910 году доказал математик Юлиус Пал.
Также он доказал, что среди кругов лучше результат получить нельзя - если радиус круга меньше, чем sqrt(3)/3, то можно предъявить такой многоугольник диаметра 1, который в этот круг не влезет (это доступно старшекласснику).
А если искать покрышки не среди кругов, а среди всех фигур? Какая из покрышек имеет наименьшую площадь?
Этот вопрос поставил в 1914 году французский математик Анри Лебег в беседе с Юлиусом Палом. Пал доказал, что от круга радиуса sqrt(3)/3 можно отрезать небольшие сегменты - и результат все равно останется покрышкой для всех многоугольников диаметра 1. За 20 век от его примера еще 3 раза другие математики отрезали кусочки (доказывая, что остаток все равно является покрышкой). Но спрашивается, достигнут ли уже минимум площади? Или можно что-то еще отрезать? Или можно какую-то совсем другую фигуру предъявить, еще меньшей площади, которая является покрышкой?
Этого никто не знает. Если хочешь узнать подробнее, хорошая, но несколько устаревшая статья по-русски -- в приложении. Она в формате tiff. В некоторых программах тиф-файлы показываются только первой страницей. Если так, то смени программу или открой на маке (файл содержит 4 страницы).
По-английски можно прочитать актуальные на сегодня результаты (или посмотреть картинки, если читать сложно):
1. наилучшая известная оценка снизу 0.832, доказана в 2005 году http://www.cs.cmu.edu/~mehrbod/UC05.pdf
авторы с помощью компьютера нашли наименьшую выпуклую фигуру, которой можно покрыть правильный треугольник, круг и правильный пятиугольник - это и есть их оценка
2. наилучшая известная оценка сверху 0.8440935944 доказана в 2018 году https://vixra.org/abs/1801.0292 (на этой странице можно скачать pdf)
3. история вопроса http://mathoverflow.net/questions/31315/is-lebesgues-universal-covering-problem-still-open
Предполагаю, что оба способа (и для оценки снизу, и для сверху) еще далеко не выработали свой максимум. Собственно, свежесть результатов это показывает - все еще впереди. Мне кажется вполне реальным, чтобы ты написал программу, которая улучшит один из этих результатов. Особенно это мне кажется вероятным в отношении оценки снизу.
P.S. В некоторых статьях говорят о минимальной покрышке для всех фигур диаметра 1, а не только для многоугольников. Диаметров фигуры называется максимальное расстояние между ее точками. Доказано, что эти задачи имеют одинаковый ответ: минимальная покрышка для всех фигур диаметра 1 и минимальная покрышка для многоугольников диаметра 1 - это одна и та же фигура (неизвестная нам). Доказано, что минимальная выпуклая покрышка существует (это доказал российский математик Михаил Ковалев). Но какова она? Эту загадку человечеству еще предстоит разгадать.
P.S.2 При более детальном рассмотрении задача делится на две подзадачи. Можно искать минимальную выпуклую покрышку, а можно искать минимальную невыпуклую покрышку (многоугольники в обоих случаях разрешаются какие угодно). Предположительно минимальная невыпуклая покрышка окажется меньше площади, чем минимальная выпуклая - но точно этого не знает никто. Текст выше касается первой из задач (ищем минимальную выпуклую покрышку).
Определим функцию S от трёх переменных (сдвиг по x, сдвиг по y, угол поворота φ), которая на выходе даёт площадь выпуклой оболочки этих 2 треугольников с соответствующими x,y,φ.
Задача 1. написать программу, которая проверит численно и ответит: унимодальна S(x,y,φ) или нет?
Определим функцию Lebesgue от 6 переменных, которая получает на вход 2 треугольника, заданных длинами сторон и выдаёт на выходе минимальное возможное S по всем значениям x,y,φ.
Задача 2. Программа получает на вход два треугольника и на выходе выдаёт
- для каждого из возможных компонент связности взаимных расположений треугольников: какой минимум функции S достигается и на каком взаимном расположении?
- из всех этих минимумов: какой самый маленький? (это будет Lebesgue от них).
Программу для п.2 можно писать двумя способами:
2а) численно
2б) выписав в явном виде функцию (для каждой компоненты связности эта функция будет частным двух полиномов) и обработав её аналитически
На первом шаге нужно написать так, как проще.
Задача 3. Попробовать переоткрыть результат Ковалёва: найти минимальную выпуклую покрышку для треугольников диаметра 1.
В зависимости от того, с какой скоростью работает программа из п.2 нужно применять разные способы. Простейший: кидать случайно разные пары треугольников диаметра 1 и смотреть S от этой пары треугольников. Попытаться угадать ответ. Потом для каждой из угаданных гипотез об ответе - пробовать совать в неё другие треугольники диаметра 1.
Задача 4. Попробовать создать новый результат - найти минимальную выпуклую покрышку для всех четырёхугольников диаметра 1. Она существует - но как выглядит, никто не знает.
Справочно.
1) Формула для площади треугольника - многочлен от 6 переменных (координаты x,y трёх вершин)
Для каждой конкретной компоненты связности модуль раскрывается либо в плюс, либо в минус.
2) Формула поворота точки на угол φ вокруг начала координат:
3) Что такое "компонента связности взаимных расположений треугольников".
Прямые, образующие треугольник А, делят плоскость на 7 частей. Каждая из вершин треугольника B может лежать в одной из этих 7 частей. Это даёт 7^3 вариантов.
Аналогично прямые, образующие треугольник B, делят плоскость на 7 частей. Каждая из вершин треугольника A может лежать в одной из этих 7 частей. Это даёт 7^3 вариантов.
Итого теоретически возможны 7^6 вариантов ≈ 100 тысяч.
В реальности почти все из них не реализуются. Проверить, какие реализуются, можно так: весь возможный шаг по x разделить на 100 шажков. Так же по y и по φ. Итого рассмотреть 10^6 возможных картинок. Для каждой из этого миллиона картинок посчитать слепок из 18 плюс-минус единиц - знак площади ориентированного треугольника A1-B1-B2 и аналогичных (одна вершина взята из одного треугольника, две - из другого). Если у двух картинок эти слепки совпадают - они в одной компоненте связности.
Подробнее о проблеме Лебега в целом:
Назовем диаметром многоугольника длину наибольшей его стороны или диагонали. Для проверки понимания: у правильного треугольника с диаметром 1 сторона равна 1. А у квадрата диаметром 1 сторона равна sqrt(2)/2.
Рассмотрим круг с радиусом 1. Можно доказать, что этим кругом можно покрыть любой многоугольник диаметра 1 (докажи!). А можно ли этот круг уменьшить (с сохранением свойства) ? Да. Более сложно, но можно доказать, что и меньший круг, радиуса sqrt(3)/3 также является покрышкой для любого многоугольника диаметра 1. Это в 1910 году доказал математик Юлиус Пал.
Также он доказал, что среди кругов лучше результат получить нельзя - если радиус круга меньше, чем sqrt(3)/3, то можно предъявить такой многоугольник диаметра 1, который в этот круг не влезет (это доступно старшекласснику).
А если искать покрышки не среди кругов, а среди всех фигур? Какая из покрышек имеет наименьшую площадь?
Этот вопрос поставил в 1914 году французский математик Анри Лебег в беседе с Юлиусом Палом. Пал доказал, что от круга радиуса sqrt(3)/3 можно отрезать небольшие сегменты - и результат все равно останется покрышкой для всех многоугольников диаметра 1. За 20 век от его примера еще 3 раза другие математики отрезали кусочки (доказывая, что остаток все равно является покрышкой). Но спрашивается, достигнут ли уже минимум площади? Или можно что-то еще отрезать? Или можно какую-то совсем другую фигуру предъявить, еще меньшей площади, которая является покрышкой?
Этого никто не знает. Если хочешь узнать подробнее, хорошая, но несколько устаревшая статья по-русски -- в приложении. Она в формате tiff. В некоторых программах тиф-файлы показываются только первой страницей. Если так, то смени программу или открой на маке (файл содержит 4 страницы).
По-английски можно прочитать актуальные на сегодня результаты (или посмотреть картинки, если читать сложно):
1. наилучшая известная оценка снизу 0.832, доказана в 2005 году http://www.cs.cmu.edu/~mehrbod/UC05.pdf
авторы с помощью компьютера нашли наименьшую выпуклую фигуру, которой можно покрыть правильный треугольник, круг и правильный пятиугольник - это и есть их оценка
2. наилучшая известная оценка сверху 0.8440935944 доказана в 2018 году https://vixra.org/abs/1801.0292 (на этой странице можно скачать pdf)
3. история вопроса http://mathoverflow.net/questions/31315/is-lebesgues-universal-covering-problem-still-open
Предполагаю, что оба способа (и для оценки снизу, и для сверху) еще далеко не выработали свой максимум. Собственно, свежесть результатов это показывает - все еще впереди. Мне кажется вполне реальным, чтобы ты написал программу, которая улучшит один из этих результатов. Особенно это мне кажется вероятным в отношении оценки снизу.
P.S. В некоторых статьях говорят о минимальной покрышке для всех фигур диаметра 1, а не только для многоугольников. Диаметров фигуры называется максимальное расстояние между ее точками. Доказано, что эти задачи имеют одинаковый ответ: минимальная покрышка для всех фигур диаметра 1 и минимальная покрышка для многоугольников диаметра 1 - это одна и та же фигура (неизвестная нам). Доказано, что минимальная выпуклая покрышка существует (это доказал российский математик Михаил Ковалев). Но какова она? Эту загадку человечеству еще предстоит разгадать.
P.S.2 При более детальном рассмотрении задача делится на две подзадачи. Можно искать минимальную выпуклую покрышку, а можно искать минимальную невыпуклую покрышку (многоугольники в обоих случаях разрешаются какие угодно). Предположительно минимальная невыпуклая покрышка окажется меньше площади, чем минимальная выпуклая - но точно этого не знает никто. Текст выше касается первой из задач (ищем минимальную выпуклую покрышку).