Расположение линий

Симплициальное расположение линий (слева) и простое расположение линий (справа).

В геометрии расположение линий — это разделение плоскости, образованной набором линий . Проблемы подсчета особенностей устройств изучались в дискретной геометрии , а вычислительная геометрия нашла алгоритмы эффективного построения устройств.

Определение

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

1. Ячейки . или камеры устройства представляют собой двумерные области, не являющиеся частью какой-либо линии Они образуют внутренности ограниченных выпуклых многоугольников или неограниченных выпуклых областей. Если плоскость разрезана по всем прямым, то это компоненты связности точек, которые остаются неразрезанными.
2. Края . или панели композиции представляют собой одномерные области, принадлежащие одной линии Это открытые отрезки линий и открытые бесконечные лучи, на которые каждая линия разделена точками пересечения с другими линиями. То есть, если одна из прямых пересечена всеми остальными прямыми, то это компоненты связности ее неразрезанных точек.
3. Вершины расположения — это изолированные точки, принадлежащие двум или более линиям, где эти линии пересекаются.

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

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

Сложность аранжировок

Изучение аранжировок было начато Якобом Штайнером , который доказал первые границы максимального числа признаков разных типов, которые может иметь аранжировка. Наиболее простыми объектами для подсчета являются вершины, ребра и ячейки:

• Договоренность с $n$ линий имеет не более $n(n-1)/2$ вершины ( треугольное число ), по одной на пару пересекающихся линий. Этот максимум достигается для простых компоновок , в которых каждые две линии пересекаются в вершине, не пересекающейся со всеми остальными линиями. Количество вершин меньше, если некоторые линии параллельны или когда некоторые вершины пересекаются более чем двумя прямыми.
• Любую компоновку можно вращать, чтобы избежать линий, параллельных осям, без изменения количества ячеек. Любое расположение без линий, параллельных осям, имеет $n$ бесконечные нисходящие лучи, по одному на линию. Эти лучи разделяются $n+1$ ячейки расположения, неограниченные в направлении вниз. Остальные ячейки имеют уникальную самую нижнюю вершину (опять же, потому что здесь нет линий, параллельных осям). Для каждой пары линий может быть только одна ячейка, где две линии встречаются в нижней вершине, поэтому количество ячеек, ограниченных вниз, не превышает количества пар линий, $n(n-1)/2$. Если сложить неограниченные и ограниченные ячейки, общее количество ячеек в расположении может составить не более $n(n+1)/2+1$. Это номера последовательности ленивого поставщика провизии .
• Число ребер компоновки не более $n^{2}$, в чем можно убедиться, либо используя эйлерову характеристику для ее вычисления по числу вершин и ячеек, либо наблюдая, что каждая линия разбита не более чем на $n$ края у другого $n-1$ линии. Опять же, эта граница наихудшего случая достигается для простых схем.

Более сложные функции называются «зонами», «уровнями» и «многоликими»:

• Зона ​ линии ​ $\ell$ в линейном расположении — это совокупность ячеек, ребра которых принадлежат $\ell$. Теорема о зоне утверждает, что общее количество ребер в ячейках одной зоны линейно. Точнее, общее количество ребер ячеек, принадлежащих одной стороне линии. $\ell$ самое большее $5n-1$, и общее количество ребер ячеек, принадлежащих обеим сторонам $\ell$ самое большее $\lfloor 9.5n\rfloor -1$. В более общем смысле, общая сложность ячеек расположения линий, пересекаемых любой выпуклой кривой, равна $O(n\alpha (n))$, где $\alpha$ обозначает обратную функцию Аккермана , как можно показать с помощью последовательностей Давенпорта-Шинзеля . Сумма квадратов сложностей ячеек в расположении равна $O(n^{2})$, что можно показать, суммируя зоны всех линий.
• The $k$- уровень расположения – это многоугольная цепочка, образованная ребрами, имеющими ровно $k$ другие строки непосредственно под ними. $\leq k$-уровень – это часть структуры ниже уровня $k$-уровень. Нахождение совпадающих верхних и нижних оценок сложности $k$-уровень остается основной открытой проблемой в дискретной геометрии. Лучшая верхняя граница $O(nk^{1/3})$, а лучшая нижняя граница равна $n2^{\Omega ({\sqrt {\log k}})}$. Напротив, максимальная сложность $\leq k$-уровень, как известно , $\Theta (nk)$. А $k$-уровень — это частный случай монотонного пути в аранжировке; то есть последовательность ребер, пересекающая любую вертикальную линию в одной точке. Однако монотонные пути могут быть гораздо сложнее, чем $k$-уровни: в этих расположениях существуют расположения и монотонные пути, в которых число точек, в которых путь меняет направление, равно $n^{2-o(1)}$.
• Хотя одна ячейка в структуре может быть ограничена всеми $n$ линий, это вообще невозможно для $m$ разные ячейки, чтобы все были ограничены $n$ линии. Скорее, общая сложность $m$ клетки не более $\Theta (m^{2/3}n^{2/3}+n)$, почти та же граница, что и в теореме Семереди–Троттера точек и прямых об инцидентности на плоскости. Простое доказательство этого следует из неравенства числа пересечений : если $m$ клетки имеют в общей сложности $x+n$ ребра, можно построить граф с $m$ узлы (по одному на ячейку) и $x$ ребра (по одному на пару последовательных ячеек в одной строке). Ребра этого графа можно нарисовать в виде кривых, которые не пересекаются внутри ячеек, соответствующих их концам, а затем следуют линиям расположения. Поэтому существуют $O(n^{2})$ пересечения на этом рисунке. Однако в силу неравенства числа пересечений существуют $\Omega (x^{3}/m^{2})$ переправы. Чтобы удовлетворить обе границы, $x$ должно быть $O(m^{2/3}n^{2/3})$.

механизмы и

удобно изучать, Расположение прямых на проективной плоскости поскольку каждая пара прямых имеет точку пересечения. Расположение линий невозможно определить с помощью сторон линий, поскольку линия в проективной плоскости не разделяет плоскость на две отдельные стороны. Можно по-прежнему определить ячейки расположения как связные компоненты точек, не принадлежащих какой-либо линии, ребра — как связные компоненты наборов точек, принадлежащих одной линии, а вершины — как точки, в которых две или более линии пересекаются. Расположение линий на проективной плоскости отличается от своего евклидова аналога тем, что два евклидовых луча на обоих концах линии заменяются одним ребром в проективной плоскости, которое соединяет крайнюю левую и крайнюю правую вершины на этой прямой, и в этом пары неограниченные евклидовы клетки заменяются в проективной плоскости одиночными клетками, которые пересекаются проективной линией на бесконечности.

Благодаря проективной двойственности многие утверждения о комбинаторных свойствах точек на плоскости легче понять в эквивалентной двойственной форме о расположении прямых. Например, теорема Сильвестра-Галлаи , утверждающая, что любой неколлинеарный набор точек на плоскости имеет обычную линию, содержащую ровно две точки, преобразуется в условиях проективной двойственности в утверждение, что любое проективное расположение конечного числа прямых с более чем одной вершиной имеет обычную точку , вершину, где пересекаются только две прямые. Самое раннее известное доказательство теоремы Сильвестра-Галлаи, выполненное Мельхиором (1940) , использует характеристику Эйлера , чтобы показать, что такая вершина должна существовать всегда.

Треугольники в аранжировках

Симплициальное расположение, образованное 20 линиями, сторонами и осями симметрии правильного десятиугольника . Добавление бесконечной линии дает еще одну симплициальную компоновку с 21 линией.

Расположение прямых на проективной плоскости называется симплициальным , если каждая ячейка расположения ограничена ровно тремя ребрами. Симплициальные устройства были впервые изучены Мельхиором. Известны три бесконечных семейства симплициальных расположений прямых:

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

Кроме того, существует множество других примеров спорадических симплициальных расположений , которые не вписываются ни в одно известное бесконечное семейство. Как пишет Бранко Грюнбаум , симплициальные договоренности «выступают в качестве примеров или контрпримеров во многих контекстах комбинаторной геометрии и ее приложений». Например, Артес, Грюнбаум и Ллибре (1998) используют симплициальные схемы для построения контрпримеров к гипотезе о связи между степенью набора дифференциальных уравнений и количеством инвариантных прямых, которые эти уравнения могут иметь. Два известных контрпримера к гипотезе Дирака–Моцкина (которая утверждает, что любой $n$-линейное расположение имеет как минимум $n/2$ обычные точки) обе симплициальны.

Двойной граф линейного расположения имеет один узел на ячейку и одно ребро, соединяющее любую пару ячеек, которые имеют общее ребро расположения. Эти графы представляют собой частичные кубы , графы, в которых узлы могут быть помечены битовыми векторами таким образом, чтобы расстояние в графе равнялось расстоянию Хэмминга между метками. В случае линейного расположения каждая координата маркировки присваивает 0 узлам на одной стороне одной из линий и 1 узлам на другой стороне. Двойственные графы симплициальных расположений использовались для построения бесконечных семейств 3-правильных частичных кубов, изоморфных графам простых зоноэдров .

Расположение с минимальным количеством треугольников согласно теореме Робертса о треугольнике.

Треугольники Кобон в расположении из 17 линий.

Также представляет интерес изучение экстремальных чисел треугольных ячеек в расположениях, которые не обязательно могут быть симплициальными. Любое расположение в проективной плоскости должно иметь не менее $n$ треугольники. Каждая аранжировка, имеющая только $n$ треугольники должны быть простыми. Для евклидовой, а не проективной компоновки минимальное количество треугольников равно $n-2$, по теореме Робертса о треугольнике . Известно, что максимально возможное число треугольных граней в простой компоновке ограничено сверху выражением $n(n-1)/3$ и снизу ограничен $n(n-3)/3$; нижняя оценка достигается некоторыми подмножествами диагоналей регулярного $2n$-гон. Для непростых компоновок максимальное количество треугольников аналогично, но более тесно ограничено. Тесно связанная проблема треугольника Кобона требует максимального количества непересекающихся конечных треугольников в расположении на евклидовой плоскости, не считая неограниченных граней, которые могут образовывать треугольники на проективной плоскости. Для некоторых, но не для всех значений $n$, $n(n-2)/3$ возможны треугольники.

Мультисетки и ромбовидные мозаики

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

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

Квадратная плитка Тетракис

Треугольная плитка

Биссектрисовая шестиугольная плитка

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

Алгоритмы

Построение компоновки означает, что, учитывая в качестве входных данных список линий в компоновке, вычисляется представление вершин, ребер и ячеек компоновки вместе со смежностями между этими объектами, например, в виде двусвязного списка ребер . Благодаря теореме о зонах, расположения могут быть эффективно построены с помощью пошагового алгоритма, который добавляет по одной строке за раз к расположению ранее добавленных строк: каждая новая линия может быть добавлена ​​за время, пропорциональное ее зоне, что приводит к общему времени построения. из $O(n^{2})$. Однако требования к памяти для этого алгоритма высоки, поэтому может быть удобнее сообщать обо всех особенностях расположения с помощью алгоритма, который не хранит всю структуру в памяти сразу. Это снова можно будет сделать эффективно, со временем. $O(n^{2})$ и космос $O(n)$ известного с помощью алгоритмического метода, как топологическая очистка . Точное вычисление расположения линий требует числовой точности, в несколько раз превышающей точность входных координат: если линия задана двумя точками на ней, координатам вершин расположения может потребоваться в четыре раза большая точность, чем этим входным точкам. Поэтому вычислительные геометры также изучали алгоритмы эффективного построения устройств с ограниченной числовой точностью.

Кроме того, исследователи изучили эффективные алгоритмы построения небольших частей композиции, таких как зоны, $k$-уровни, или набор ячеек, содержащий заданный набор точек. Задача нахождения вершины расположения с медианой $x$-координата возникает (в двойственной форме) в робастной статистике как задача вычисления оценки Тейла – Сена набора точек.

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

Расположение неевклидовых линий

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

Расположение гиперболических линий, комбинаторно эквивалентное хордовой диаграмме, использованной Агеевым (1996) , чтобы показать, что без треугольников круговым графикам иногда может потребоваться 5 цветов .

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

Другой тип неевклидовой геометрии — гиперболическая плоскость , и расположение гиперболических линий в этой геометрии также изучалось. Любой конечный набор прямых в евклидовой плоскости имеет комбинаторно эквивалентное расположение в гиперболической плоскости (например, путем заключения вершин расположения в большой круг и интерпретации внутренней части круга как модели Клейна гиперболической плоскости). Однако параллельные (непересекающиеся) пары прямых менее ограничены в расположении гиперболических линий, чем в евклидовой плоскости: в частности, отношение параллельности является отношением эквивалентности для евклидовых линий, но не для гиперболических линий. Граф пересечения линий в гиперболическом расположении может быть произвольным круговым графом . Соответствующей концепцией гиперболического расположения псевдолиний является слабое расположение псевдолиний , семейство кривых, имеющих те же топологические свойства, что и линии такие, что любые две кривые в семействе либо встречаются в одной точке пересечения, либо не имеют пересечений.

См. также

• Конфигурация (геометрия) , расположение линий и набор точек, при этом все линии содержат одинаковое количество точек и все точки принадлежат одному и тому же количеству линий.
• Расположение (разделение пространства) — разделение плоскости, заданной наложенными кривыми, или пространства более высокой размерности наложенными поверхностями, без требования, чтобы кривые или поверхности были плоскими.
• Математический мост — мост в Кембридже, Англия, балки которого образуют касательные линии к его арке.

Ссылки

• Абраменко, Петр; Браун, Кеннет С. (2008), Здания: теория и применение , Тексты для выпускников по математике, том. 248, Нью-Йорк: Спрингер, номер домена : 10.1007/978-0-387-78835-7 , ISBN.  978-0-387-78834-0 , МР   2439729 ; см. пример 10.14, стр. 519–520.
• Агарвал, ПК (1990), «Разделение линий II: Приложения», Дискретная и вычислительная геометрия , 5 (1): 533–573, doi : 10.1007/BF02187809
• Агарвал, ПК ; де Берг, М .; Матушек, Ю. ; Шварцкопф, О. (1998), «Построение уровней в устройствах и диаграммах Вороного высшего порядка», SIAM Journal on Computing , 27 (3): 654–667, CiteSeerX   10.1.1.51.5064 , doi : 10.1137/S0097539795281840
• Агарвал, ПК ; Матушек, Ю. ; Шарир, М. (1998), «Вычисление множества граней в расположении прямых и сегментов», SIAM Journal on Computing , 27 (2): 491–505, doi : 10.1137/S009753979426616X , hdl : 1874/17088
• Агарвал, ПК ; Шарир, М. (2000), «Устройства и их применение» (PDF) , в Саке, Ж.-Р. ; Уррутиа, Дж. (ред.), Справочник по вычислительной геометрии , Elsevier, стр. 49–119, заархивировано (PDF) из оригинала 11 апреля 2021 г. , получено 11 ноября 2018 г.
• Агарвал, ПК ; Шарир, М. (2002), «Псевдолинейные устройства: двойственность, алгоритмы и приложения» , Proc. 13-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '02) , Сан-Франциско: Общество промышленной и прикладной математики, стр. 800–809.
• Агеев, А.А. (1996), «Круговой граф без треугольников с хроматическим числом 5», Дискретная математика , 152 (1–3): 295–298, doi : 10.1016/0012-365X(95)00349-2
• Ахарони, Ю.; Гальперин, Д.; Ханниел, И.; Хар-Пелед, С. ; Линхарт, К. (1999), «Построение зон в режиме онлайн при расположении линий на плоскости», Виттер , Джеффри С .; Заролиагис, Христос Д. (ред.), Разработка алгоритмов: 3-й международный семинар, WAE'99, Лондон, Великобритания, 19–21 июля 1999 г., Труды , конспекты лекций по информатике, том. 1668, Springer-Verlag, стр. 139–153 , CiteSeerX   10.1.1.35.7681 , doi : 10.1007/3-540-48318-7_13 , ISBN  978-3-540-66427-7
• Аджтай, М. ; Хватал, В. ; Ньюборн, М. ; Семереди, Э. (1982), «Подграфы без скрещиваний», Теория и практика комбинаторики , Математические исследования Северной Голландии, том. 60, Северная Голландия, стр. 9–12, MR   0806962.
• Алон, Н. ; Дьёри, Э. (1986), «Число малых полупространств конечного набора точек на плоскости», Журнал комбинаторной теории, серия A , 41 : 154–157, doi : 10.1016/0097-3165 (86 )90122-6
• Аронов, Б. ; Матушек, Ю. ; Шарир, М. (1994), «О сумме квадратов сложностей ячеек в расположении гиперплоскостей», Журнал комбинаторной теории, серия A , 65 (2): 311–321, doi : 10.1016/0097-3165(94)90027 -2
• Артес, JC; Грюнбаум, Б .; Ллибре, Дж. (1998), «О количестве инвариантных прямых для полиномиальных дифференциальных систем» (PDF) , Pacific Journal of Mathematics , 184 (2): 207–230, doi : 10.2140/pjm.1998.184.207 , в архиве (PDF) из оригинала от 18 июля 2010 г. , получено 15 декабря 2008 г.
• Балог, Дж.; Регев, О.; Смит, К.; Штайгер, В.; Сегеди, М. (2004), «Длинные монотонные пути в линейных расположениях», Discrete & Computational Geometry , 32 (2): 167–176, doi : 10.1007/s00454-004-1119-1
• Берн, МВт; Эппштейн, Д .; Плассман, ЧП; Яо, Ф.Ф. (1991), «Теоремы о горизонте для линий и многоугольников», в Гудмане, Дж. Э .; Поллак, Р.; Штайгер, В. (ред.), Дискретная и вычислительная геометрия: статьи специального года DIMACS , DIMACS Ser. Дискретная математика. и теоретическая информатика (6-е изд.), Amer. Математика. Соц., стр. 45–66, МР   1143288.
• Борвейн, П. ; Мозер, WOJ (1990), «Обзор проблемы Сильвестра и ее обобщений», Aequationes Mathematicae , 40 (1): 111–135, doi : 10.1007/BF02112289 , MR   1069788 , S2CID   122052678
• Бозе, П. ; Эванс, В.; Киркпатрик, генеральный директор ; Макаллистер, М.; Снойинк, Дж. (1996), "Аппроксимация кратчайших путей в расположении прямых", Proc. 8-я Канадская конференция. Вычислительная геометрия , стр. 143–148.
• де Брейн, Н.Г. (1981), «Алгебраическая теория непериодических разбиений плоскости Пенроуза» (PDF) , Indagationes Mathematicae , 43 : 38–66, заархивировано (PDF) из оригинала 07 мая 2021 г. , получено в 2008 г. -12-14
• Кэнхэм, Р.Дж. (1969), «Теорема о расположении линий на плоскости», Израильский математический журнал , 7 (4): 393–397, doi : 10.1007/BF02788872 , S2CID   123541779
• Чан, Т. (1999), Замечания об алгоритмах k -уровня на плоскости , заархивировано из оригинала 4 ноября 2010 г.
• Шазель, Б. ; Гибас, LJ ; Ли, Д.Т. (1985), «Сила геометрической двойственности», BIT Numerical Mathematics , 25 (1): 76–90, doi : 10.1007/BF01934990 , S2CID   122411548
• Кларксон, К .; Эдельсбруннер, Х. ; Гибас, LJ ; Шарир, М .; Вельцль, Э. (1990), «Оценки комбинаторной сложности расположения кривых и сфер», Discrete & Computational Geometry , 5 (1): 99–160, doi : 10.1007/BF02187783
• Коул, Ричард; Салове, Джеффри С.; Штайгер, В.Л.; Семереди, Эндре (1989), «Алгоритм оптимального времени для выбора наклона», SIAM Journal on Computing , 18 (4): 792–810, doi : 10.1137/0218055 , MR   1004799
• Коул, Р.; Шарир, М .; Яп, К.-К. (1987), «О k -корпусах и связанных с ними проблемах», SIAM Journal on Computing , 16 (1): 61–77, doi : 10.1137/0216005
• Кроу, Д.В.; Макки, Т. А. (1968), «Проблема Сильвестра о коллинеарных точках», Mathematics Magazine , 41 (1): 30–34, doi : 10.2307/2687957 , JSTOR   2687957
• Дей, Т.Л. (1998), «Улучшенные границы для плоских k- множеств и связанных с ними проблем», Discrete & Computational Geometry , 19 (3): 373–382, doi : 10.1007/PL00009354 , MR   1608878
• Дирак, Г. (1951), «Свойства коллинеарности множеств точек», Ежеквартальный журнал математики , 2 (1): 221–227, Бибкод : 1951QJMat...2..221D , doi : 10.1093/qmath/2.1. 221
• Платье, А.; Кулен, Дж. Х.; Моултон, В. (2002), «Онлайн-расположения в гиперболической плоскости», Европейский журнал комбинаторики , 23 (5): 549–557, doi : 10.1006/eujc.2002.0582 , MR   1931939
• Эдельсбруннер, Х. (1987), Алгоритмы в комбинаторной геометрии , Монографии EATCS по теоретической информатике, Springer-Verlag, ISBN  978-3-540-13722-1
• Эдельсбруннер, Х. ; Гибас, LJ (1989), «Топологически охватывающее расположение», Журнал компьютерных и системных наук , 38 (1): 165–194, doi : 10.1016/0022-0000(89)90038-X
• Эдельсбруннер, Х. ; Гибас, LJ ; Шарир, М. (1990), «Сложность и построение многих граней в расположении прямых и сегментов», Discrete & Computational Geometry , 5 (1): 161–196, doi : 10.1007/BF02187784
• Эдельсбруннер, Х. ; О'Рурк, Дж .; Зайдель, Р. (1986), «Построение расположения линий и гиперплоскостей с применением», SIAM Journal on Computing , 15 (2): 341–363, doi : 10.1137/0215024
• Эдельсбруннер, Х. ; Вельцль, Э. (1986), «Построение ремней в двумерных конструкциях с приложениями», SIAM Journal on Computing , 15 (1): 271–284, doi : 10.1137/0215019
• Эппштейн, Д. (2006), «Кубические частичные кубы из симплициальных расположений» , Electronic Journal of Combinatorics , 13 (1, R79): 1–14, arXiv : math.CO/0510263 , doi : 10.37236/1105 , MR   2255421 , S2CID   8608953 , заархивировано из оригинала 14 февраля 2012 г. , получено 14 декабря 2008 г.
• Эппштейн, Д .; Фальмань, Ж.-Кл. ; Овчинников, С. (2007), Теория СМИ , Springer-Verlag.
• Эппштейн, Д .; Харт, Д. (1999), «Кратчайшие пути в расположении с ориентацией k линий» , Труды 10-го симпозиума ACM – SIAM по дискретным алгоритмам (SODA '99) , стр. 310–316.
• Эрдеш, П .; Ловас, Л. ; Симмонс, А.; Штраус, Э. Г. (1973), «Графы разрезания множеств плоских точек», Обзор комбинаторной теории (Proc. Internat. Sympos., Университет штата Колорадо, Форт-Коллинз, Колорадо, 1971) , Амстердам: Северная Голландия, стр. 139–149, МР   0363986.
• Эриксон, Дж. (1997), Кратчайшие пути в расположении строк , заархивировано из оригинала 3 декабря 2008 г. , получено 15 декабря 2008 г.
• Фортуна, С.; Миленкович, В. (1991), "Численная устойчивость алгоритмов построения строк", Proc. 7-й симпозиум ACM по вычислительной геометрии (SoCG '91) , стр. 334–341, CiteSeerX   10.1.1.56.2404 , doi : 10.1145/109648.109685 , ISBN  978-0897914260 , S2CID   2861855
• де Фрейссе, Х.; Оссона де Мендес, П. (2003), «Растяжение контактных систем жордановой дуги», Труды 11-го Международного симпозиума по рисованию графов (GD 2003) , Конспекты лекций по информатике (изд. 2912 г.), Springer-Verlag, стр. 71–85
• Фюреди, З. ; Паласти, И. (1984), «Расположение линий с большим количеством треугольников» (PDF) , Proceedings of the American Mathematical Society , 92 (4): 561–566, doi : 10.2307/2045427 , JSTOR   2045427 , в архиве ( PDF) из оригинала 3 марта 2016 г. , получено 15 декабря 2008 г.
• Гудман, Джейкоб Э .; Поллак, Ричард (1993), «Допустимые последовательности и типы порядка в дискретной и вычислительной геометрии», в Пач, Янош (ред.), Новые тенденции в дискретной и вычислительной геометрии , алгоритмы и комбинаторика, том. 10, Берлин: Springer, стр. 103–134, номер документа : 10.1007/978-3-642-58043-7_6 , MR   1228041.
• Гудман, Джейкоб Э .; Поллак, Ричард ; Венгер, Рефаэль; Замфиреску, Тюдор (1994), «Каждая договоренность распространяется на спред», Combinatorica , 14 (3): 301–306, doi : 10.1007/BF01212978 , MR   1305899 , S2CID   42055590
• Грин, Д.; Яо, Ф.Ф. (1986), «Вычислительная геометрия конечного разрешения», Труды 27-го симпозиума IEEE по основам информатики (FOCS '86) , стр. 143–152, doi : 10.1109/SFCS.1986.19 , ISBN  978-0-8186-0740-0 , S2CID   2624319
• Грюнбаум, Б. (1972), Расположение и распространение , Серия региональных конференций по математике, том. 10, Провиденс, Род-Айленд: Американское математическое общество.
• Грюнбаум, Б. (1974), Заметки о договоренностях , Вашингтонский университет, hdl : 1773/15699 ; см. стр. 6 из «Евклидовых механизмов» (стр. 101 связанного PDF-файла)
• Грюнбаум, Бранко (2009), «Каталог симплициальных расположений в вещественной проективной плоскости», Ars Mathematica Contemporanea , 2 (1): 1–25, doi : 10.26493/1855-3974.88.e12 , hdl : 1773/2269 , MR   2485643
• Гальперин, Д.; Шарир, М. (2018), «Аранжировки», Гудман, Джейкоб Э.; О'Рурк, Джозеф; Тот, Чаба Д. (ред.), Справочник по дискретной и вычислительной геометрии , Дискретная математика и ее приложения (3-е изд.), Бока-Ратон, Флорида: CRC Press, стр. 723–762, ISBN  978-1-4987-1139-5 , МР   3793131
• Келли, LM ; Мозер, WOJ (1958), «О количестве обычных линий, определяемых n точками», Canadian Journal of Mathematics , 10 : 210–219, doi : 10.4153/CJM-1958-024-6
• Клее, Р. (1938), О простых конфигурациях евклидовых и проективных плоскостей , Дрезден: Focken & Oltmanns.
• Лейтон, FT (1983), Проблемы сложности в СБИС , Серия «Основы вычислений», Кембридж, Массачусетс: MIT Press
• Леви, Ф. (1926), «Деление проективной плоскости линией или псевдолинией», Ber. Матем.-Физ. Кл. Академическая наука Лейпциг , 78 : 256–267.
• Ловас, Л. (1971), «О количестве разделенных пополам линий», Annales Universitat Scientiarum Buddhainensis de Rolando Eőtvős Nominata Mathematical Division , 14 : 107–108
• Мартин, Джордж Э. (1996), Основы геометрии и неевклидова плоскость , Тексты для студентов по математике, Springer-Verlag, ISBN  0-387-90694-0 , МР   1410263
• Матушек, Дж. (1991), «Нижние границы длины монотонных путей в устройствах», Discrete & Computational Geometry , 6 (1): 129–134, doi : 10.1007/BF02574679
• Мельхиор, Э. (1940), «Об универсальности проективной плоскости», German Mathematics , 5 : 461–475.
• Миленкович, В. (1989), «Геометрия двойной точности: общий метод расчета пересечений линий и сегментов с использованием округленной арифметики», Труды 30-го симпозиума IEEE по основам компьютерных наук (FOCS '89) , стр. 500–505, doi : 10.1109/SFCS.1989.63525 , ISBN  978-0-8186-1982-3 , S2CID   18564700
• Морено, Хосе Педро; Прието-Мартинес, Луис Фелипе (2021), «Проблема треугольников Кобона», La Gaceta de la Real Sociedad Matemática Española (на испанском языке), 24 (1): 111–130, hdl : 10486/705416 , MR   4225268
• Моцкин, Т. (1951), «Линии и плоскости, соединяющие точки конечного множества», Труды Американского математического общества , 70 (3): 451–464, doi : 10.2307/1990609 , JSTOR   1990609
• Овчинников, Сергей (2011), Графики и кубы , Universitext, Нью-Йорк: Springer, doi : 10.1007/978-1-4614-0797-3 , ISBN  978-1-4614-0796-6 , МР   3014880
• Польстер, Буркард (1998), Книга с геометрическими картинками , Universitext, Springer-Verlag, Нью-Йорк, номер документа : 10.1007/978-1-4419-8526-2 , ISBN  0-387-98437-2 , МР   1640615
• Перди, ГБ (1979), «Треугольники в расположении прямых», Discrete Mathematics , 25 (2): 157–163, doi : 10.1016/0012-365X(79)90018-9
• Перди, ГБ (1980), «Треугольники в расположении прямых, II», Труды Американского математического общества , 79 : 77–81, doi : 10.1090/S0002-9939-1980-0560588-4
• Руднев, Ж.-П. (1988), «Расположение линий с минимальным количеством треугольников просто», Discrete & Computational Geometry , 3 (1): 97–102, doi : 10.1007/BF02187900
• Шефер, Маркус (2010), «Сложность некоторых геометрических и топологических задач» (PDF) , Рисование графиков, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Переработанные статьи , Конспекты лекций по информатике, том. 5849, Springer-Verlag, стр. 334–344, номер doi : 10.1007/978-3-642-11805-0_32 , ISBN.  978-3-642-11804-3 , заархивировано (PDF) из оригинала 26 июня 2021 г. , получено 25 февраля 2011 г.
• Шор, П.В. (1991), «Растяжимость псевдолиний NP-трудна», у Грицманна, П.; Штурмфельс, Б. (ред.), Прикладная геометрия и дискретная математика: The Victor Klee Festschrift , Серия DIMACS по дискретной математике и теоретической информатике, том. 4, Провиденс, Род-Айленд: Американское математическое общество, стр. 531–554.
• Штайнер, Дж. (1826), «Некоторые законы разделения плоскостей и пространств», Дж. Рейн Ангью. Math. , 1 : 349–364, doi : 10.1515/crll.1826.1.349 , S2CID   120477563 .
• Строммер, Т.О. (1977), «Треугольники в расположении прямых», Журнал комбинаторной теории, серия A , 23 (3): 314–320, doi : 10.1016/0097-3165(77)90022-X
• Секели, Л.А. (1997), «Числа пересечения и сложные проблемы Эрдеша в дискретной геометрии» (PDF) , Combinatorics, Probability and Computing , 6 (3): 353–358, doi : 10.1017/S0963548397002976 , S2CID   36602807 , в архиве (PDF) из оригинала от 8 августа 2017 г. , получено 23 сентября 2019 г.
• Тот, Г. (2001), «Множества точек со многими k -множествами», Discrete & Computational Geometry , 26 (2): 187–194, doi : 10.1007/s004540010022

Внешние ссылки

• База данных комбинаторно различных расположений линий