Введение

Задача геометрии на точках сетки. Задача о расположении точек без трех на одной прямой в дискретной геометрии спрашивает, какое максимальное количество точек можно разместить в сетке так, чтобы никакие три точки не лежали на одной прямой. Задача касается прямых любого наклона, а не только прямых, выровненных по сетке. Она была предложена Генри Дюденеем в 1900 году. Брасс, Мозер и Пач называют её «одним из старейших и наиболее изученных геометрических вопросов, касающихся точек решётки». Максимальное количество точек, которые можно разместить, ограничено, поскольку в сетке размещение точек неизбежно приведет к появлению ряда из трех или более точек на одной прямой, согласно принципу Дирихле. Хотя задача может быть решена для каждого до , предполагается, что в сетках большого размера можно разместить менее чем 100 точек. Известные методы позволяют размещать линейно много точек в сетках произвольного размера, но лучшие из этих методов размещают чуть меньше точек, чем . Также были изучены несколько связанных задач о поиске точек, не лежащих на одной прямой, среди других наборов точек, отличных от сеток. Хотя задача о расположении точек без трех на одной прямой возникла в рекреационной математике, она имеет приложения в построении графов и в задаче о треугольнике Гейльбронна.

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

Точное число точек, которые можно разместить, как функция от , неизвестно. Однако как доказанные, так и предполагаемые оценки ограничивают это число диапазоном, пропорциональным .

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

Решение Пола Эрдоша, опубликованное в , основано на наблюдении, что когда — простое число, множество точек сетки по модулю , для , не содержит трех коллинеарных точек. Когда не является простым, можно выполнить эту конструкцию для сетки, содержащейся в сетке , где — наибольшее простое число, не превосходящее . Поскольку расстояние между последовательными простыми числами значительно меньше самих простых чисел, всегда будет близко к , поэтому этот метод можно использовать для размещения точек в сетке так, чтобы никакие три точки не лежали на одной прямой. Граница Эрдоша впоследствии была улучшена: показали, что когда — простое число, можно получить решение с точками, размещая точки в нескольких копиях гиперболы (mod ), где можно выбирать произвольно, пока оно отлично от нуля по модулю . Аналогично, для произвольного можно выполнить эту конструкцию для простого числа, близкого к , чтобы получить решение с .

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

В сетку любого размера можно поместить максимум точек. Если поместить больше точек, то по принципу Дирихле (или принципу голубиных ящиков) некоторые три из них обязательно окажутся на одной горизонтальной линии сетки. Для этого тривиального ограничения известно, что оно является точным.

Приложения

Решения задачи о расположении точек, не лежащих на одной прямой, могут быть использованы для избежания определенных видов вырождений при построении графов. Задача, к которой они применимы, заключается в размещении вершин заданного графа в целочисленных координатах на плоскости и рисовании ребер графа в виде отрезков прямых. Для некоторых графов, таких как граф полезности, пересечения между парами ребер неизбежны, но все равно следует избегать размещений, при которых вершина лежит на ребре, проходящем через две другие вершины. Когда вершины размещены так, что никакие три не лежат на одной прямой, подобное проблемное размещение не может возникнуть, поскольку вся прямая, проходящая через любые две вершины, а не только отрезок прямой, свободна от других вершин. Тот факт, что задача о расположении точек, не лежащих на одной прямой, имеет решение с линейным числом точек, можно перевести на язык построения графов как утверждение о том, что любой граф, даже полный граф, можно нарисовать без нежелательных инциденций вершин и ребер, используя сетку, площадь которой квадратична относительно числа вершин, и что для полных графов невозможно построить такое изображение с площадью, меньшей квадратичной. Полные графы также требуют линейного числа цветов при любом раскрашивании графа, но другие графы, которые можно раскрасить меньшим числом цветов, также можно нарисовать на сетках меньшего размера: если граф имеет *n* вершин и раскрашен *k* цветами, то его можно нарисовать на сетке с площадью, пропорциональной *n*/*k*. Построение полного графа без трех точек на одной прямой является частным случаем этого результата.

Задача о расположении точек, не лежащих на одной прямой, также имеет применение к другой задаче в дискретной геометрии – задаче Гейльбронна о треугольниках. В этой задаче необходимо разместить *n* точек где угодно в единичном квадрате, не ограничиваясь сеткой. Цель размещения – избежать треугольников с малой площадью, а точнее – максимизировать площадь наименьшего треугольника, образованного тремя точками. Например, размещение с тремя точками на одной прямой было бы очень плохим по этому критерию, поскольку эти три точки образовали бы вырожденный треугольник с нулевой площадью. С другой стороны, если точки можно разместить на сетке со стороной единичной длины внутри единичного квадрата, так чтобы никакие три точки не лежали на одной прямой, то по теореме Пика каждый треугольник будет иметь площадь не менее 1/2, то есть половину площади ячейки сетки. Следовательно, решение экземпляра задачи о расположении точек, не лежащих на одной прямой, а затем масштабирование целочисленной сетки для соответствия единичному квадрату дает решения задачи Гейльбронна о треугольниках, где площадь наименьшего треугольника равна 1/2. Это приложение послужило мотивацией для Пола Эрдеша найти решение задачи о расположении точек, не лежащих на одной прямой. Оно оставалось лучшей известной нижней границей площади для задачи Гейльбронна о треугольниках с 1951 по 1982 год, когда оно было улучшено на логарифмический фактор с использованием построения, не основанного на задаче о расположении точек, не лежащих на одной прямой.

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

В вычислительной геометрии конечные множества точек, в которых никакие три точки не лежат на одной прямой, называются находящимися в общем положении. В этой терминологии задача "отсутствия трех точек на одной прямой" заключается в поиске наибольшего подмножества сетки, находящегося в общем положении, однако исследователи также рассматривали задачу поиска наибольшего подмножества в общем положении для других наборов точек, не являющихся сетками. Найти такое подмножество сложно для определенных входных наборов, и сложно приближенно оценить его размер с точностью до постоянного множителя; эта сложность приближения обобщается утверждением, что задача является APX-сложной. Если наибольшее подмножество имеет размер *k*, то решение с неконстантным коэффициентом приближения можно получить с помощью жадного алгоритма, который просто выбирает точки по одной, пока все оставшиеся точки не окажутся на прямых, проходящих через пары выбранных точек. Можно получить более детальное понимание времени работы алгоритмов для поиска точного оптимального решения, используя параметризованную сложность, в которой алгоритмы анализируются не только с точки зрения размера входных данных, но и с точки зрения других параметров входных данных. В этом случае, для входных данных, наибольшее подмножество в общем положении которых имеет размер *k*, его можно найти за время, являющееся экспоненциальной функцией от *k*, умноженной на полином от размера входных данных *n*, при этом степень полинома не зависит от *n*. Задачи с такими ограничениями по времени называются параметрически разрешимыми (fixed-parameter tractable). Для наборов точек, содержащих не более *ℓ* точек на одной прямой, где *ℓ* = O(√*n*), существуют подмножества в общем положении, размер которых почти пропорционален *ℓ* = O(√*n*). Пример сетки показывает, что эту границу нельзя существенно улучшить. Доказательство существования этих больших подмножеств в общем положении можно преобразовать в алгоритм полиномиального времени для поиска подмножества в общем положении размера, соответствующего границе существования, используя алгоритмическую технику, известную как сжатие энтропии.

Жадный размещение

Повторяя предложение, Мартин Гарднер попросил найти наименьшее подмножество сетки n x n, которое нельзя расширить: в нем нет трех точек на одной прямой, но любое собственное надмножество содержит три точки на одной прямой. Эквивалентно, это наименьший набор, который может быть получен жадным алгоритмом, пытающимся решить задачу о расположении точек так, чтобы не было трех на одной прямой, путем последовательного добавления точек, пока алгоритм не зайдёт в тупик. Если рассматривать только прямые, параллельные осям, и диагонали, то каждый такой набор содержит не менее n точек. Однако о версии задачи, где рассматриваются все прямые, известно меньше: каждое жадное размещение включает не менее n точек, прежде чем алгоритм зайдёт в тупик, но лучшей верхней границы, чем тривиальная, пока не найдено.

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

Они доказали, что максимальное количество точек в трехмерной сетке, не лежащих на одной прямой, равно. Подобно конструкции Эрдеша для двумерного случая, этого можно достичь, используя точки по модулю , где – простое число, сравнимое с 3 по модулю 4. Как и исходная задача о расположении трех точек на одной прямой может быть использована для двумерного рисования графов, так и это трехмерное решение можно использовать для рисования графов в трехмерной сетке. Здесь условие неколлинеарности означает, что вершина не должна лежать на ребре, не смежном с другими, хотя обычно работают с более строгим требованием, чтобы никакие два ребра не пересекались. В гораздо больших размерностях множества точек сетки, не лежащих на одной прямой, полученные путем выбора точек вблизи гиперсферы, использовались для поиска больших множеств Салема — Спенсера, то есть множеств целых чисел, в которых никакие три не образуют арифметическую прогрессию. Однако использование той же идеи выбора точек вблизи окружности в двух измерениях не дает хороших результатов: этот метод находит точки, образующие выпуклые многоугольники, которые удовлетворяют требованию неколлинеарности, но слишком малы. Наибольшие выпуклые многоугольники с вершинами в сетке имеют только вершин. Задача о множестве чемоданов связана с проблемой, аналогичной задаче о расположении трех точек на одной прямой, в пространствах высокой размерности, основанных на векторных пространствах над конечными полями, а не над целыми числами. Другое обобщение для более высоких размерностей — найти максимально возможное количество точек в трехмерной сетке, чтобы никакие четыре из них не лежали в одной плоскости. Эта последовательность начинается с 5, 8, 10, 13, 16, для и т.д.

Торос

Другая вариация проблемы заключается в преобразовании сетки в дискретный тор, используя периодические граничные условия, при которых левая сторона тора соединена с правой, а верхняя – с нижней. Это приводит к тому, что наклонные линии, проходящие через сетку, объединяются в более длинные линии, содержащие больше точек, что затрудняет выбор точек так, чтобы на каждой линии было не более двух точек. Эти расширенные линии также можно интерпретировать как прямые линии, проходящие через бесконечную сетку в евклидовой плоскости, рассматриваемые по модулю размеров тора. Для тора, основанного на сетке, максимальное количество точек, которые можно выбрать без трех точек на одной прямой, составляет не более . Когда оба измерения равны и являются простыми числами, невозможно разместить ровно одну точку в каждой строке и каждом столбце, не образовав линейное количество коллинеарных троек. Также изучались многомерные варианты этой проблемы для торов.