Математик научила таксистов объезжать Манхэттен по ровному кругу и измерять число π

Математик Мишель Рудольф-Лилит из Национального центра научных исследований Франции описала особенности окружностей, начерченных в дискретном пространстве, в качестве примера которого ученый рассмотрела пересечения улиц и проспектов Манхэттена — центрального района Нью-Йорка. Оказалось, что можно аналитически описать несколько алгоритмов, следуя которым, гипотетический таксист проедет вдоль линии, максимально приближенной к идеальной окружности, а при достаточно большом ее радиусе можно с хорошей точностью измерить число π. Исследование в виде препринта выложено на arXiv.org.
В математике есть понятие «норма», простейший смысл которого — это расстояние (или, точнее, длина вектора) в некотором пространстве. В жизни мы чаще всего пользуемся евклидовой нормой, которая для плоскости очень похожа на теорему Пифагора. Чтобы найти расстояние от некоторого центра с координатами (0,0) до точки с координатами А (x,y), проведем в эту точку вектор OA. Квадрат его нормы ||OA||2 = x2 + y2 и будет равен квадрату расстояния до точки А.
Но как быть, если мы находимся в дискретном пространстве? Например, как рассказывает Рудольф-Лилит, все в том же Манхэттене расстояние от одной точки до другой по прямой может быть 4,3 мили, но на самом деле кратчайший маршрут составит около 6 миль, ведь ехать можно только по улицам и проспектам, которые пересекаются под прямым углом. В этом случае пространство можно задать как множество точек, соответствующее перекресткам. Тогда любой маршрут будет задаваться линией, которую мы проведем по этим точкам, причем использовать диагонали нельзя.
Вопрос, который поднимает математик в своей работе, состоит в том, как правильно задать окружность в дискретном множестве точек, и можно ли с помощью таких окружностей точно определить число π? Первая проблема тесно связана, например, с компьютерной графикой, где все окружности (и кривые линии в целом) нужно отрисовывать на дискретном пространстве пикселей, то есть растеризовать. Разумеется, сама прикладная задача давно решена, однако ряд математических свойств этих решений остался неизученным.
Чтобы избежать непонимания, автор подчеркнула, что изучаться будет именно привычная нам окружность, которую для центра в (0,0) и радиуса R можно задать параметрически как множество точек, удовлетворяющих x2 + y2 = R2. «Дискретная» окружность тогда будет задаваться как множество точек в дискретном пространстве, лежащих как можно ближе к «настоящей» окружности. Автор приводит широко используемые алгоритмы, в частности mid-point и signum, которые давно и успешно используются для черчения таких дискретных окружностей. Рудольф-Лилит отмечает, что «таксисту будет несложно прокатить пассажира „по кругу“, в уме вычисляя, куда повернуть на том или ином перекрестке».
Тем не менее, автор показывает, что с увеличением радиуса воображаемой окружности точность определения числа π через отношение длины окружности к диаметру растет. Для окружности радиусом в десять перекрестков можно определить π с точностью до третьего знака после запятой, а для радиуса в 1000000 перекрестков — до девятого знака. Рудольф-Лилит не только сделала численное моделирование, но получила необходимые аналитические выражения, которые показывают справедливость ее утверждений в предельном переходе к бесконечному радиусу.
Число π — один из любимых объектов математиков. Эту иррациональную константу можно измерить многими, часто неординарными способами: например, бросая иголки на стол или стреляя 200 раз из дробовика Mossberg 500. А четырнадцатого марта (03/14 в формате дат, принятом в США) по всему миру традиционно отмечается день числа π.
Тарас Молотилин