Не-трехрядная проблема - No-three-in-line problem

Задача « no-three-in-line» в дискретной геометрии спрашивает, сколько точек можно разместить в сетке, чтобы никакие три точки не лежали на одной линии. Это число не больше , потому что точки в сетке будут включать ряд из трех или более точек по принципу ячейки . Эта проблема была предложена Генри Дудени в 1900 году. Брасс, Мозер и Пах называют ее «одним из старейших и наиболее широко изученных геометрических вопросов, касающихся точек решетки». ${\ Displaystyle п \ раз п}$${\ displaystyle 2n}$${\ displaystyle 2n + 1}$

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

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

Небольшие экземпляры

Впервые эта задача была поставлена Генри Дудени в 1900 году как головоломка из развлекательной математики, сформулированная в терминах размещения 16 пешек шахматной доски на доске так, чтобы никакие три пешки не стояли на одной линии. В данном случае это как раз и есть проблема отсутствия трех рядов . ${\ displaystyle n = 8}$В более поздней версии головоломки Дудени изменил задачу, сделав ее решение уникальным, запросив решение, в котором две пешки находятся на полях d4 и e5 и атакуют друг друга в центре доски.

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

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

Точное количество точек , которые могут быть размещены, как функция от ,${\ displaystyle n}$ не известно. Тем не менее, оба доказанных и высказано предположение , границы ограничивают этот номер в пределах диапазона , пропорциональный к .${\ displaystyle n}$

Общие способы размещения

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

Граница Эрдеша была впоследствии улучшена: Hall et al. (1975) показывают, что, когда простое число, можно получить решение с точками, помещая точки в несколько копий гиперболы (mod ), где может быть выбрано произвольно, если оно не равно нулю mod . Опять же, для произвольного можно выполнить это построение для простого числа вблизи, чтобы получить решение с точками.${\ displaystyle n / 2}$${\ Displaystyle 3 (п-2) / 2}$ ${\ displaystyle xy = k}$ ${\ displaystyle n / 2}$${\ displaystyle k}$${\ displaystyle n / 2}$${\ displaystyle n}$${\ displaystyle n / 2}$${\ displaystyle {\ tfrac {3} {2}} нет (п)}$

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

Максимальное количество точек может быть помещено в сетку любого размера . Ведь если разместить больше точек, то по принципу «ячеек» некоторые три из них все будут лежать на одной и той же горизонтальной линии сетки. Для малых достаточно значений из , это тривиальная границы плотно. ${\ displaystyle 2n}$${\ displaystyle n}$${\ displaystyle n}$

Предполагаемые оценки

Хотя точно точки могут быть размещены на малых сетках, Гай и Келли (1968) предположили, что для больших сеток существует значительно меньшая верхняя граница количества точек, которые могут быть размещены. Точнее, они высказали предположение , что число точек , которые могут быть помещены в самом большем количество сублинейно больше , чем , с ${\ displaystyle 2n}$${\ displaystyle cn}$

После того, как ошибка в эвристическом рассуждении, ведущая к этой гипотезе, была обнаружена, Гай исправил ошибку и высказал более сильную гипотезу, что нельзя делать больше, чем сублинейно лучше, чем с ${\ displaystyle cn}$

Приложения

Чтобы избежать определенных видов вырождений при рисовании графов, можно использовать решения проблемы «no-three-in-line» . Проблема, к которой они обращаются, включает размещение вершин данного графа в целочисленных координатах на плоскости и рисование ребер графа в виде отрезков прямых линий . Для некоторых графов, таких как служебный граф , пересечения между парами ребер неизбежны, но все же следует избегать размещения, которое заставляет вершину лежать на ребре через две другие вершины. Когда вершины размещаются без трех в линии, такого рода проблемное размещение не может возникнуть, потому что вся линия, проходящая через любые две вершины, а не только сегмент линии, свободна от других вершин. Тот факт, что у задачи без трех рядов есть решение с линейно большим количеством точек, можно перевести в термины рисования графа, как означающие, что каждый граф, даже полный граф , может быть нарисован без нежелательных столкновений вершин и ребер с использованием сетки, Площадь квадратична по количеству вершин, и для полных графов рисование с площадью меньше квадратичной невозможно. Полные графики также требуют линейного количества цветов в любом раскраски графа , но и другие графики , которые могут быть окрашены с меньшим количеством цветов также могут быть нарисованы на небольших сетках: если граф имеет вершины и раскраску граф с цветами, это можно сделать в сетка с площадью , пропорциональной к . Рисование полного графика без трех линий - частный случай этого результата с .${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle nk}$${\ Displaystyle к = п}$

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

Обобщения и вариации

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

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

Более детальное понимание времени работы алгоритмов поиска точного оптимального решения можно получить, используя параметризованную сложность , в которой алгоритмы анализируются не только с точки зрения размера входных данных, но и с точки зрения других параметров входных данных. В этом случае для входных данных, наибольшее подмножество общего положения которых имеет размер ,${\ displaystyle k}$ его можно найти за время, которое является экспоненциальной функцией, умноженной на полином от входного размера , причем показатель степени полинома не зависит от . Проблемы с такими временными рамками называются решаемыми с фиксированными параметрами . ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle k}$

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

Жадное размещение

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

Высшие измерения

Неколлинеарные наборы точек в трехмерной сетке рассматривались Пор и Вуд (2007) . Они доказали , что максимальное число точек в сетке, без трех точек коллинеарны является . Подобно двухмерному построению Эрдеша, это может быть достигнуто с помощью модуля точек , где - простое число, конгруэнтное 3 по модулю 4 . Подобно тому, как исходная задача «no-three-in-line» может использоваться для рисования двухмерных графиков, можно использовать это трехмерное решение для рисования графиков в трехмерной сетке. Здесь условие неколлинеарности означает, что вершина не должна лежать на несмежном ребре, но нормально работать с более строгим требованием, чтобы никакие два ребра не пересекались. ${\ Displaystyle п \ раз п}$${\ Displaystyle \ Theta (п ^ {2})}$${\ Displaystyle (х, у, х ^ {2} + у ^ {2}}$${\ displaystyle p)}$${\ displaystyle p}$

В гораздо более высоких измерениях наборы точек сетки без трех на одной линии, полученные путем выбора точек около гиперсферы , использовались для нахождения больших множеств Салема – Спенсера , наборов целых чисел без трех, образующих арифметическую прогрессию. Однако использовать ту же идею выбора точек около круга в двух измерениях не очень хорошо: этот метод находит точки, образующие выпуклые многоугольники, которые удовлетворяют требованию не иметь трех на линии, но слишком малы. Самые большие выпуклые многоугольники с вершинами в сетке имеют только вершины. Проблема набора заглавных букв связана с проблемой, аналогичной проблеме отсутствия трех рядов в пространствах, которые одновременно являются многомерными и основаны как векторные пространства над конечными полями, а не над целыми числами. ${\ Displaystyle п \ раз п}$${\ Displaystyle О (п ^ {2/3})}$

Тор

Другой вариант проблемы заключается в преобразовании сетки в дискретный тор с использованием периодических граничных условий, в которых левая сторона тора соединяется с правой стороной, а верхняя сторона соединяется с нижней стороной. Это приводит к соединению наклонных линий через сетку в более длинные линии через большее количество точек и, следовательно, затрудняет выбор точек с максимум двумя из каждой линии. Эти удлиненные линии также можно интерпретировать как нормальные линии через бесконечную сетку на евклидовой плоскости, взятые по модулю размеров тора. Для тора, основанного на сетке, максимальное количество точек, которые могут быть выбраны без трех на линии, не больше . Когда оба измерения равны и просты, невозможно разместить ровно одну точку в каждой строке и столбце, не образуя линейное количество коллинеарных троек. Изучены также многомерные торовые версии задачи. ${\ Displaystyle м \ раз п}$${\ Displaystyle 2 \ НОД (т, п)}$

Примечания

использованная литература

внешняя ссылка

• Фламменкамп, Ахим. «Проблема отсутствия трех рядов» .
• Вайсштейн, Эрик В. "Проблема без тройки в строке" . MathWorld .