Задача «никакие три на прямой»

Множество из 20 точек в решётке 10 × 10, никакие три из которых не находятся на одной прямой.

Задача «никакие три точки не лежат на одной прямой» — одна из задач комбинаторной геометрии, состоящая в нахождении количества точек, которые можно расположить на решётке $n\times n$ так, чтобы никакие три точки не находились на одной прямой.

Брасс, Мозер и Пах назвали задачу «одним из самых старых и интенсивно изучаемых геометрических вопросов, касающихся точек решётки».

Проблему можно решить с $2n$ точками для любого $n$ до $46$, однако существует гипотеза, что на решётках большего размера можно разместить менее $2n$ точек. Известные методы могут разместить линейное количество точек на решётке произвольного размера, но лучшие методы размещают меньше, чем $3n/2$ точек, а совсем не $2n$. Изучались также проблемы поиска точек, среди которых никакие три не находятся на одной прямой, включая множества точек, отличные от решёток.

Хотя первоначально проблема появилась как задача занимательной математики, она имеет приложение в визуализации графов и в проблеме треугольников Хайльбронна.

Малые размеры

Задачу впервые опубликовал Генри Эрнест Дьюдени в 1900 году как головоломку занимательной математики в терминах размещения 16 пешек на шахматной доске так, что никакие три пешки не находятся на одной прямой. Это в точности проблема «никакие три на прямой» для $n=8$. В более поздних версиях головоломки Генри изменил задачу, делающее решение единственным, требуя найти решение, когда две пешки уже на доске поставлены в клетки d4 и e5 в центре доски.

Много авторов публиковали решения задачи для малых значений $n$ и к 1998 году было известно, что $2n$ точек может быть размещено на решётке $n\times n$ без трёх точек на прямой для всех $n$ до 46 и некоторых бо́льших значений. Число решений (не включая отражения и вращения) для малых значений $n$, начиная с $n=2$, равно

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, … (последовательность A000769 в OEIS).

Верхняя и нижняя границы

Функция от $n$, которая бы выражала точное число точек, неизвестна, однако, как доказанные, так и гипотетические пределы этого числа линейно пропорциональны $n$.

Общие методы размещения

Близкое к оптимальному размещение $11$ точек на решётке $12\times 12$ при использовании метода Эрдёша. Наибольшее простое число $p$, меньшее размера решётки равно $p=11$. Решение размешает точки на координатах $(i,i^{2}$ по подулю $p)$ для $i=0,1,\dots p-1$. Например, точка $(4,5)$ включена, поскольку $4^{2}=16\cong 5$ по модулю $11$.

Решение Пала Эрдёша, опубликованное Ротом, основано на факте, что, когда $n$ является простым числом, множество из $n$ точек решётки $(i,i^{2}$ по модулю $n)$ для $0\leqslant i<n$ не содержит трёх коллинеарных точек. Если $n$ является простым числом, можно осуществить такое построение для решётки $p\times p$, содержащейся в решётке $n\times n$, где $p$ является наибольшим простым числом, меньшим $n$. Поскольку интервалы между простыми числами много меньше самих простых чисел, $p$ будет всегда близко к $n$, так что этот метод может быть использован, чтобы поместить $n-o(n)$ точек на $n\times n$ решётке при условии, что никакие три точки не коллинеарны.

Граница впоследствии была улучшена — Холл, Джексон, Садбери и Уилд показали, что в случае простого $n/2$ можно получить решение с $3(n-2)/2$ точками, размещая точки в копиях гиперболы $xy=k$ (по модулю $n/2$), где $k$ можно задать произвольным образом с ограничением, что оно не должно равняться нулю по модулю $n/2$. Снова, для произвольного $n$ можно осуществить это построение для простого числа, близкого к $n/2$, чтобы получить решение с ${\tfrac {3}{2}}n-o(n)$ точками.

Верхняя граница

На решётке любого размера $n$ может быть размещено не более $2n$ точек, так как при размещении большего количества по принципу Дирихле какие-то три из них окажутся на какой-то горизонтальной линии решётки. Для $n\leqslant 46$, известно, что эта тривиальная граница точна.

Гипотетические границы

Хотя в точности $2n$ точек можно разместить в небольших решётках, есть гипотеза, что для больших решёток существует существенно меньшая верхняя граница на число точек, которые можно разместить в решётке. Точнее, есть предположение, что максимальное число точек, которые могут быть размещены на решётке, не более чем сублинейно больше значения $cn$ при

$$c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1{,}874.$$

После обнаружения ошибки в эвристических рассуждениях, приведших к данной гипотезе, Гай исправил ошибку и высказал предположение, что граница не может быть сублинейно лучше значения $cn$ для

$$c={\frac {\pi }{\sqrt {3}}}\approx 1{,}814.$$

Приложения

Приложения проблемы «никакие три на прямой» могут быть использованы для избежания некоторого рода вырождений в визуализации графов. Так, она используется для размещения вершин заданного графа на плоскости в точках с целочисленными координатами, рёбра между которыми при этом изображаются отрезками. Для некоторых графов, таких как коммунальный граф, пересечение пар рёбер избежать нельзя, но можно избежать размещения вершины на ребре между двумя другими вершинами. Если расположить вершины со свойством «никакие три на прямой», такого рода проблемное расположение не сможет возникнуть, поскольку любая прямая будет содержать только две вершины. Факт, что задача «никакие три точки на прямой» имеет решение с линейным числом точек, можно перевести в термины визуализации графов, что означает, что любой граф, даже полный, можно нарисовать без нежелательных попаданий вершин на рёбра с использованием решётки, площадь которой зависит квадратично от числа вершин, а для полных графов нет никакого такого рисования графов с менее чем квадратичной площадью. Для полных графов требуется линейное число цветов в любой раскраске графа, но другие графы, которые можно раскрасить с меньшим числом цветов можно нарисовать на меньших решётках — если граф имеет $n$ вершин и раскрашен в $k$ цветов, он может быть нарисован на решётке с площадью, пропорциональной $nk$. Рисование полных графов с условием «никакие три на прямой» является специальным случаем этого результата с $k=n$.

Проблема «никакие три на прямой» имеет также приложение к другой задаче дискретной геометрии, проблеме треугольников Хайльбронна. В этой задаче нужно расположить $n$ точек в единичном квадрате, не ограничивая расположения решёткой. Целью является такое расположение, чтобы избежать треугольников малой площади, а точнее, максимизировать площадь наименьшего треугольника, образованного тремя точками. Например, размещение трёх точек на прямой было бы крайне неудачным с точки зрения этого критерия, поскольку эти три точки образуют треугольник нулевой площади. С другой стороны, если точки расположить на решётке со стороной $\varepsilon$ внутри единичного квадрата так, что никакие три точки не располагаются на прямой, то по формуле Пика любой треугольник будет иметь площадь не менее $\varepsilon ^{2}/2$, половину площади квадрата решётки. Таким образом, решив задачу «никакие три на прямой» и уменьшения размеров целочисленной решётки, чтобы вместить решение в единичных квадрат, получаем решения проблемы треугольников Хайльбронна, где наименьший треугольник имеет площадь $\Omega (1/n^{2})$. Это приложение побудило Пала Эрдёша найти решение для задачи «никакие три на прямой» Такое решение оставалось лучшей нижней границей площади, известной для проблемы треугольников Хайльбронна с 1951 до 1982, когда было улучшено на логарифмический множитель с помощью построения, которое не использует решение задачи «никакие три на прямой».

Обобщения и варианты

Подмножества общего вида

В вычислительной геометрии конечные множества точек со свойством, что никакие три точки не лежат на прямой, называются множествами в общем положении. В этой терминологии задача «никакие три на прямой» ищет наибольшее подмножество решётки в общем положении, но исследователи также рассматривают задачи нахождения наибольшего подмножества в общей позиции других множеств точек, не являющихся решётками. Поиск такого подмножества является NP-трудной задачей для определённых входных множеств и трудно аппроксимировать их размер с постоянным коэффициентом. Эта сложность аппроксимации суммируется высказыванием, что задача APX-трудна. Если наибольшее подмножество имеет размер $k$, решение с непостоянным аппроксимационным коэффициентом $O({\sqrt {k}})$ может быть получено с помощью жадного алгоритма, который просто выбирает точки по одной пока не окажется, что все оставшиеся точки лежат на прямой, проходящей через какую-либо пару выбранных точек.

Можно получить более точные алгоритмы для нахождения точного оптимального решения путём использования параметризованной сложности. В этих алгоритмах анализ производится не только в терминах входного размера, но и в терминах других параметров входа. В этом случае для входных данных, наибольшее подмножество которого в общей позиции имеет размер $k$, решение может быть найдено за время, зависящее экспоненциально от $k$, умноженное на многочлен размера $n$ со степенью многочлена, не зависящей от $k$. Задачи с такого рода границами по времени называются фиксированно-параметрически разрешимыми.

Для множеств точек $S$, имеющих не более ${\textstyle \ell }$ точек на любой прямой, с ${\textstyle \ell =O({\sqrt {|S|}})}$, существуют подмножества в общей позиции размера, почти пропорционального ${\textstyle \ell =O({\sqrt {|S|}})}$. Пример решётки показывает, что граница не может быть существенно улучшена. Доказательство существования этих больших подмножеств в общем положении может быть преобразовано в алгоритм полиномиального времени нахождения подмножества $S$ общего положения размера, равного границе существования, с помощью алгоритмической техники, известной как энтропийное сжатие.

Жадный алгоритм размещения

Повторяя предложение Адена, Холтона и Келли, Гарднер, Мартин задаёт вопрос наименьшего подмножества решётки $n\times n$, которое не может быть расширено — оно не имеет трёх точек на прямой, но любое собственное надмножество имеет три на линии. Эквивалентно, это наименьшее множество, которое получает жадный алгоритм, который пытается решить задачу «никакие три на прямой» путём размещения точек по одной, пока не застопорится. Если рассматриваются только прямые, параллельные осям, то любое такое множество имеет по крайней мере $n-1$ точек. Однако меньше известно о версии проблемы, в которой рассматриваются все прямые: любой жадный алгоритм размещения включает по меньшей мере $\Omega (n^{2/3})$ точек перед остановом, но ничего не известно лучше, чем тривиальная верхняя граница $2n$.

Более высокие размерности

Неколлинеарные множества точек на трёхмерной решётке рассматривали Пор и Вуд. Они доказали, что максимальное число точек на решётке $n\times n\times n$ со свойством, что никакие три точки не коллинеарны, равно $\Theta (n^{2})$. Аналогично двумерному построению Эрдёша можно осуществить размещение точек $(x,y,x^{2}+y^{2}$ по модулю $p)$, где $p$ является простым числом, сравнимым с 3 по модулю 4. Так же как оригинальная задача «никакие три на прямой» может быть использована для двумерной визуализации графов, можно использовать трёхмерное решение для отрисовки графов на трёхмерной решётке. Здесь неколлинеарность означает, что вершины не лежат на несмежных рёбрах (то есть, если вершина лежит на ребре, она должна быть его концом), но является также нормальным более строгое требование, чтобы рёбра не пересекались.

В более высоких размерностях множества точек решётки, в которых нет трёх точек на прямой, получаемые путём выбора точек близ гиперсферы, используются для нахождения больших множеств Салема — Спенсера, множеств целых чисел, не образующих арифметических прогрессий. Однако это не работает, если использовать ту же идею выбора точек, близких к окружности в двухмерном пространстве — этот метод находит точки, образующие выпуклый многоугольник, который удовлетворяет требованиям отсутствия трёх точек на одной прямой, но он слишком мал. Максимальный выпуклый многоугольник с вершинами на решётке $n\times n$ имеет только $O(n^{2/3})$ вершин. Задача множества колпаков рассматривает аналогичную проблему к проблеме «никакие три на прямой» в пространствах более высокой размерности, базирующихся на векторных пространствах над конечными полями.

Тор

Другой вариант проблемы использует преобразование решётки в дискретный тор с помощью периодических граничных условий, в которых левая сторона тора соединена с правой частью, а верхняя сторона соединена с нижней стороной. Это приводит к тому, что на косых линиях на решётке находится больше точек, а потому труднее выбрать точки с условием не более двух точек на прямой Эти расширенные прямые можно также интерпретировать как нормальные прямые через бесконечную решётку на евклидовой плоскости, взятые по модулю размерностей тора. Для тора на основе решётки $m\times n$ максимальное число точек, которые можно выбрать, чтобы никакие три точки не лежали на прямой, не превосходит $2\gcd(m,n)$. Если обе размерности одинаковы и являются простыми числами, невозможно разместить ровно по одной точке в каждой строке и столбце без формирования линейного числа коллинеарных троек. Изучалась также версия для тора высокой размерности.

Ссылки

• Flammenkamp, Achim. The No-Three-in-Line Problem  (неопр.).
• Weisstein, Eric W. No-Three-in-a-Line-Problem (англ.) на сайте Wolfram MathWorld.