1 June 2015

Наибольшие малые многогранники: новые решения в комбинаторной геометрии

Wolfram Research corporate blogEntertaining tasksProgrammingMathematics
Original author: Ed Pegg Jr

Перевод поста Ed Pegg Jr."Biggest Little Polyhedron—New Solutions in Combinatorial Geometry".
Скачать файл, содержащий текст статьи, интерактивные модели многогранников и код, приведенный в статье, можно здесь.
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

Во многих областях математики ответом будет единица 1. Возведение неотрицательного числа в квадрат, которое больше или меньше единицы, даст большее или меньшее число соответственно. Иногда для того, чтобы определить, является ли что-то «большим», необходимо выяснить, больше ли единицы наибольший размер этого объекта. К примеру, гигантский гексагон Сатурна с длиной стороны в 13,800 км можно было-бы отнести к большим. «Малый многоугольник» — это тот, у которого максимальное расстояние между вершинами равно единице. В 1975 году Рон Грэм открыл наибольший малый шестиугольник, который, как показано ниже, имеет большую площадь, чем у правильного шестиугольника. Красные диагонали имеют единичную длину. Все остальные (непроведённые) диагонали имеют меньшую длину.

Regular hexagon, biggest little hexagon, biggest little octagon showing lengths of 1

Мне всегда было интересно, как будет выглядеть самый большой малый многогранник. В Mathematica 10 был представлен новый функциональный объект Volume[ConvexHullMesh[points]], и я подумал, что можно было бы решить эту задачу, выбирая случайные точки. Ниже представлен код для выбора, вычисления и визуализации случайного малого многогранника. Тысячи раз прокрутив этот код, можно будет получить неплохое приближение в лучшем из результатов. Вот, тут я три раза запускал код. Один из результатов, вероятно, лучше остальных.

Random solutions for picking points on a polyhedron

Ниже на изображении приведены наилучшие решения, которые были получены через случайно выбранные точки. Я выложил это в Wolfram Community в обсуждении наибольший малый многогранник (далее – НММ) и получил несколько полезных комментариев от Робина Хьюстона и Тодда Роланда. Для поиска решений я решил использовать результаты "визуализации задачи Томпсона". В задаче Томсона электроны отталкиваются друг от друга на сфере. 12 отталкивающихся друг от друга точек стремятся к вершинам икосаэдра, что не эффективно для НММ, так как наибольшие расстояния проходят через центр сферы, так же как и для правильных шестиугольников в двумерном случае. Я изменил код для задачи Томпсона так, что точки отскакивали друг друга и ото всех противолежащих, и это дало неплохие начальные значения.

Starting values using modified Thomson code

Для четырёх точек решением будет правильный тетраэдр с объёмом /12= 0.117851.

Для пяти точек решением будет равносторонний треугольник с единичными длинами сторон и единичный перпендикуляр к этому треугольнику, а объём получится равным /12 = 0.1443375; это решение было получено в 1976-ом году [1].

Regular tetrahedron and equilateral triangle points

Я буду использовать термин 6-НММ для обозначения наибольшего малого многогранника с шестью точками. В 2003-ем году объём 6-НММ был вычислен с точностью до четырёх знаков [2,3]. Ниже представлены 6-НММ и 7-НММ, единичные диагонали выделены красным.

6-BLP and 7-BLP

Для того чтобы найти их самостоятельно, сперва я выбрал наилучшие варианты из более чем тысячи, а затем использовал алгоритм имитации отжига (simulated annealing) (вероятностная задача поиска хорошего приближения к глобальному оптимуму данной функции в широком пространстве поиска – прим. пер.) для улучшения результатов. Для каждой из точек оптимальных решений я перебирал пространство вокруг этих точек для поиска лучшего решения, ненамного их смещая. Затем я ещё более уменьшал пространство поиска, и так из раза в раз. Некоторые из решений, казалось, стремятся к взаимной симметричности. К примеру, для семи точек лучшее решение стремилось к этому многограннику со значением r около половины, который представляет относительный размер верхнего треугольника △456.

Symmetrical solution for random polyhedron with seven points

Точный объём можно получить через тетраэдр, который определяется через точки {{2,3,4,7}, {2,4,6,7}, {5,4,7,6}}, а объём первых двух следует утроить из соображений симметрии. Посмотрите на объёмы тетраэдров, и замените любую пару чисел в тетраэдре так, чтобы получился отрицательный объём.

Determining the exact volume of the tetrahedra by defined points

После того, как мы изменили соотношение в последнем тетраэдре, мы можем вычислить точное значение r, которое даст точный и оптимальный объём. Этим же методом воспользуемся и для других случаев.

Calculating r for solution6, solution7, solution8, solution9

Решение для 16-НММ занимает более минуты, так что мне пришлось разбить его.

Solution for 16-BLP

Первое значение в решениях — оптимальный объём, является объектом Root, а второе является оптимальным значением r. Вот, эта таблица будет поаккуратнее.

Table of values for optimal value of r

И это далеко за пределами того, что я смог бы сделать вручную. С помощью случайной выборки точек, алгоритма симуляции отжига, поиска симметрии, Solve[] и Maximize[] мне удалось найти точные значения объёмов n-НММ (наибольших малых многогранников) для n = 6, 7, 8, 9 и 16.

Вид 8-НММ с нескольких сторон, где красным выделены единичные диагонали.

Views of the 8-BLP with the red tubes showing unit-length diagonals

Вид 9-НММ с нескольких сторон:

Views of 9-BLP with the red tubes showing unit-length diagonals

Вид 16-НММ с нескольких сторон:

Views of 16-BLP with the red tubes showing unit-length diagonals

Указанный ниже 8-НММ содержит единичные перпендикуляры 1-2 и 3-4 над и под основанием соответственно. Представленный ниже 9-НММ содержит треугольники △123, △456 и △789.

8-BLP featuring perpendicular line units and 9-BLP featuring stacked triangles

Приведённый ниже 16-НММ представляет собой усечённый тетраэдр, состоящий из точек 1-12 с дополнительными точками 13-16.

16-BLP featuring a truncated tetrahedron

Довольно сложно, не так ли? С помощью метода выбора точек на сфере, случайными числами в промежутках [–Pi; Pi] и [–1; 1] на единичной сфере можно задать равномерное распределение точек. Точки на единичной сфере могут быть отображены обратно в точки в прямоугольнике [–Pi; Pi]x[–1; 1]. Вот, что произойдёт для решений 8,9,16-НММ.

Sphere point picking for solutions with 8, 9, and 16 points

Для 10-НММ мне не удалось найти точное решение, однако я могу представить численное решение с любой степенью точности. Свяжитесь со мной, если у Вас есть догадки, как тут найти root object. В исполняемой версии этой статьи на Wolfram Language в разделе инициализации можно найти это весьма нелёгкое выражение.

10-BLP equation

Тут представлены два вида 10-НММ с двух разных точек обзора.

Two different perspectives of the labeled view of 10-BLP

Численное решение для 11-НММ можно найти схожим образом.

11-BLP equation

Вид 11-НММ с двух сторон:

Two views of 11-BLP

Действительно ли я получил верные решения? Может быть и нет. Для этих симметрий я уверен, что я нашёл локальный максимум. Например, вот функция с локальным максимумом 5 при значении 1.

Plot showing found local maximum of 5

А если заглянуть в графике чуть дальше, то можно будет найти глобальный максимум 32 при значении в -2.

Plot showing found global maximum of 32

В схожей задаче Томпсона имеется доказательство для 12 вершин икосаэдра, находясь в которых система из 12 электронов находится в потенциальном минимуме. Но для 7, 8, 9, 10, 11 и 13+ электронов задача считается нерешённой. В гипотезе Кеплера предполагается, что гексагональная плотная упаковка есть плотнейшая упаковка для сфер, однако строгое доказательство было получено Томасом Хейлзом лишь 10-го августа 2014-го года. Плотнейшая упаковка для правильных тетраэдров — с отношением 4000/4671 = 0.856347… — была открыта лишь 27-го июля 2010-го года, однако до сих пор не имеет строгого доказательства. Любые заявления о найденном решении следует воспринимать с определённой долей скептицизма; геометрические задачи максимизации, как известно, очень сложны.

Несколько месяцев моё лучшее решение для 11 точек было в локальном максимуме, соответствующем асимметричному НММ. Некоторые (или большинство) из этих решений, скорее всего, локальные, а не глобальные, но какие из них? С этой оговоркой можно посмотреть на самые известные решения для 12-ти и более точек.

12-НММ имеет вершину в точке 12 и содержит в себе неправильный семиугольник 11-6-7-10-8-5-9 и четырёхугольник 1-4-3-2.

13-НММ имеет вершину в точке 13 и содержит в себе неправильный семиугольник 12-8-10-6-7-9-11 и такой же пятиугольник 1-2-3-4-5.

Мои попытки добавить симметрию привели к фигурам с меньшим объёмом.

12-BLP and 13-BLP

По идее, решения для 14-НММ должны быть весьма симметричны, однако они у меня пока-что не получились. Я потратил некоторое время на оптимизацию системы вершина-пятиугольник-пятиугольник для 15-НММ, однако методом случайных точек было получено лучшее решение, в котором симметрия была принесена в жертву объёму.

14-BLP and 15-BLP

17-НММ, 18-НММ — я надеюсь, что в первом всё в порядке с симметрией.

Что касается 19-НММ и 20-НММ, то 20-НММ — не додекаэдр, так как единичные линии из центра — не лучший вариант.

Symmetry for 17-BLP, 18-BLP, 19-BLP, and 20-BLP

Как «курносый куб» (snub cube), так и половина огромного ромбокубоктаэдра — все имеют меньший объём, чем 24-НММ.

Snub cube and half the vertices of the great rhombicuboctahedron have lower volume than 24-BLP

21-НММ и 22-НММ содержат множество семи- и девятиконечных звёзд.

23-НММ, 24-НММ — мой лучший 24-НММ имеет тетраэдрическую симметрию.

21-BLP, 22-BLP, 23-BLP, 24-BLP symmetry

Вот некоторые симметрии в текущем лучшем 24-НММ. Отрезки 1-12 и 13-24 имеют соответствующие длины 0.512593 и 0.515168.

Symmetry in the current best 24-BLP

В 16-НММ и 17-НММ единичные отрезки определяют многоугольники. 16-НММ содержит множество семиконечных звёзд.

16-BLP contains 7-pointed stars

Ниже представлены те же самые многогранники, представленные как сплошные тела, посредством ConvexHullMesh[], для НММ 9-10-11-12, 13-14-15-16, 17-18-19-20, 21-22-23-24, соответственно.

Polyhedra shown as solid objects using ConvexHullMesh

Здесь представлена таблица наилучших известных на данный момент значений.

Current table of best known values

Вот лучшие решения, которые я нашёл на данный момент, для 4-24 точек.

Best solutions for 4 to 24 points

Пусть точки будут расположены так, чтобы максимальное расстояние от начала координат было как можно меньше. Распределение, представленное ниже, указывает на расстояния от начала координат до вершин каждого многогранника, в каждом из которых от 8 до 24 вершин.

Distance from origin for vertices scatterplot

С помощью Mathematica 10.1 удалось получить точные значения для 6,7,8,9-НММ и 16-НММ. Так же с её помощью были найдены очень точные, но численные значения для 10-НММ и 11-НММ и удалось серьёзно продвинуться с 24-НММ. Таким образом, мы получили решения семи ранее нерешённых задач в комбинаторной геометрии — все, благодаря комбинации Volume[ConvexHullMesh[points]]. А какие нововведения в Mathematica 10 помогли лично Вам?

Список литературы


[1] B. Kind and P. Kleinschmidt, “On the Maximal Volume of Convex Bodies with Few Vertices,” Journal of Combinatorial Theory, Series A, 21(1) 1976 pp. 124-128.
doi:10.1016/0097-3165(76)90056-X
[2] A. Klein and M. Wessler, “The Largest Small n-dimensional Polytope with n+3 Vertices,” Journal of Combinatorial Theory, Series A, 102(2), 2003 pp. 401-409.
doi:10.1016/S0097-3165(03)00054-2
[3] A. Klein and M. Wessler, “A Correction to ‘The Largest Small n-dimensional Polytope with n+3 Vertices,’” Journal of Combinatorial Theory, Series A, 112(1), 2005 pp. 173-174.
doi:10.1016/j.jcta.2005.06.001
Tags:wolfram languagewolfram mathematicaкомбинаторная геометриямногогранникилокальная оптимизацияглобальная оптимизация
Hubs: Wolfram Research corporate blog Entertaining tasks Programming Mathematics
+16
9.7k 47
Comments 26
Popular right now
Top of the last 24 hours