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

Подразделение плоскости линиями

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

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

Определение

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

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

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

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

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

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

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

Более сложные объекты носят названия «зоны», «уровни» и «множество граней»:

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

Проективные аранжировки и проективная двойственность

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

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

Треугольники в композициях

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

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

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

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

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

Также интересно изучить экстремальные числа треугольных ячеек в расположениях, которые не обязательно могут быть симплициальными. Любое расположение в проективной плоскости должно иметь по крайней мере треугольники. Каждое расположение, которое имеет только треугольники, должно быть простым. ^[28] Для евклидовых, а не проективных расположений минимальное число треугольников равно , по теореме Робертса о треугольнике . ^[29] Известно, что максимально возможное число треугольных граней в простом расположении ограничено сверху и снизу ; нижняя граница достигается определенными подмножествами диагоналей правильного -угольника. ^[30] Для непростых расположений максимальное число треугольников аналогично, но ограничено более строго. ^[31] Тесно связанная задача о треугольнике Кобона требует максимального числа неперекрывающихся конечных треугольников в расположении в евклидовой плоскости, не считая неограниченных граней, которые могли бы образовывать треугольники в проективной плоскости. Для некоторых, но не всех значений , треугольники возможны. ^[32] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle n(n-1)/3}$ ${\displaystyle n(n-3)/3}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n(n-2)/3}$

Мультисетки и ромбические мозаики

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

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

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

Алгоритмы

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

Кроме того, исследователи изучали эффективные алгоритмы для построения меньших частей расположения, таких как зоны, ^[38] -уровни, ^[39] или набор ячеек, содержащих заданный набор точек. ^[40] Проблема нахождения вершины расположения со средней -координатой возникает (в двойственной форме) в надежной статистике как проблема вычисления оценщика Тейла–Сена набора точек. ^[41] ${\displaystyle k}$ ${\displaystyle x}$

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

Неевклидовы линейные конфигурации

Расположение псевдолиний — это семейство кривых , которые разделяют схожие топологические свойства с расположением линий. ^[45] Их можно определить наиболее просто в проективной плоскости как простые замкнутые кривые, любые две из которых встречаются в одной точке пересечения. ^[46] Расположение псевдолиний называется растяжимым, если оно комбинаторно эквивалентно расположению линий. Определение растяжимости — сложная вычислительная задача: для экзистенциальной теории действительных чисел вполне достаточно отличить растяжимые расположения от нерастягиваемых. ^[47] Каждое расположение конечного числа псевдолиний можно расширить так, чтобы они стали линиями в «распространении», типе неевклидовой геометрии инцидентности , в которой каждые две точки топологической плоскости соединены уникальной линией (как в евклидовой плоскости), но в которой другие аксиомы евклидовой геометрии могут быть неприменимы. ^[48]

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

Смотрите также

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

Примечания

1. Grünbaum (1972), стр. 4.
2. Эппштейн, Фалмань и Овчинников (2007), стр. 177–178.
3. Овчинников (2011), стр. 210.
4. Штайнер (1826); Агарвал и Шарир (2000).
5. Гальперин и Шарир (2018), стр. 724.
6. Слоан, Н. Дж. А. (ред.), «Последовательность A000124 (Центральные многоугольные числа (последовательность ленивого поставщика))», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
7. Chazelle, Guibas & Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke & Seidel (1986).
8. Берн и др. (1991); неопубликованная рукопись Рома Пинхаси от 2011 года утверждает немного более сильную связь . ${\displaystyle \lfloor 9.5n\rfloor -3}$
9. Берн и др. (1991).
10. Аронов, Матушек и Шарир (1994).
11. Dey (1998); Tóth (2001). Проблема ограничения сложности k -уровней была впервые изучена Lovász (1971) и Erdős et al. (1973).
12. Алон и Дьёри (1986).
13. Балог и др. (2004); см. также Матушек (1991).
14. Канхэм (1969); Кларксон и др. (1990).
15. Аджтай и др. (1982); Лейтон (1983).
16. Секей (1997).
17. Goodman & Pollack (1993), стр. 109 Архивировано 01.01.2023 на Wayback Machine : «Естественной средой для расположения линий является реальная проективная плоскость»
18. Польстер (1998), стр. 223.
19. Гудман и Поллак (1993), стр. 110.
20. Это самое раннее доказательство, приведенное Борвейном и Мозером (1990), но они пишут, что то же самое доказательство, вероятно, было дано «гораздо раньше другими».
21. Мельхиор (1940); Грюнбаум (2009).
22. Грюнбаум (1972); Грюнбаум (2009).
23. Грюнбаум (2009).
24. Артес, Грюнбаум и Ллибре (1998).
25. Кроу и Макки (1968); Дирак (1951); Келли и Мозер (1958); Грюнбаум (1972), стр. 18.
26. Эппштейн, Фалмейн и Овчинников (2007), стр. 180.
27. Эппштейн (2006).
28. Грюнбаум (1972); Леви (1926); Руднефф (1988).
29. Грюнбаум (1972).
30. Фюреди и Паласти (1984); Грюнбаум (1972).
31. Перди (1979); Перди (1980); Штроммер (1977).
32. Морено и Прието-Мартинес (2021).
33. Клее (1938).
34. де Брейн (1981).
35. Абраменко и Браун (2008).
36. Эдельсбруннер и Гибас (1989).
37. Форчун и Миленкович (1991); Грин и Яо (1986); Миленкович (1989).
38. Ахарони и др. (1999).
39. Агарвал и др. (1998); Чан (1999); Коул, Шарир и Яп (1987); Эдельсбруннер и Вельцль (1986).
40. Агарвал (1990); Агарвал, Матушек и Шарир (1998); Эдельсбруннер, Гибас и Шарир (1990).
41. Коул и др. (1989).
42. Эриксон (1997).
43. Бозе и др. (1996).
44. Эппштейн и Харт (1999).
45. Грюнбаум (1972); Агарвал и Шарир (2002).
46. Это определение взято из Grünbaum (1972). Для сравнения альтернативных определений псевдолиний см. Eppstein, Falmagne & Ovchinnikov (2007).
47. Шор (1991); Шефер (2010).
48. Гудман и др. (1994).
49. Платье, Кулен и Моултон (2002).
50. Мартин (1996), стр. 41, 338.
51. де Фрессейкс и Оссона де Мендес (2003).
52. Здесь уместно альтернативное определение Шора (1991), согласно которому псевдопрямая — это образ прямой при гомеоморфизме плоскости.

Ссылки

• Абраменко, Питер; Браун, Кеннет С. (2008), Здания: теория и приложения , Graduate Texts in Mathematics, т. 248, Нью-Йорк: Springer, doi : 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) в Sack, J.-R .; Urrutia, J. (ред.), Handbook of Computational Geometry , Elsevier, стр. 49–119, архивировано (PDF) из оригинала 2021-04-11 , извлечено 2024-10-16
• Агарвал, П. К.; Шарир , М. (2002), «Псевдолинейные конфигурации: дуальность, алгоритмы и приложения», Труды 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
• Ajtai, M. ; Chvátal, V. ; Newborn, M. ; Szemerédi, E. (1982), "Crossing-free subgraphs", Теория и практика комбинаторики , North-Holland Mathematics Studies, т. 60, North-Holland, стр. 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
• Артес, Дж. К.; Грюнбаум, Б.; Ллибре, Дж. (1998), «О числе инвариантных прямых линий для полиномиальных дифференциальных систем» (PDF) , Pacific Journal of Mathematics , 184 (2): 207–230, doi : 10.2140/pjm.1998.184.207 , архивировано из оригинала (PDF) 18.07.2010 , извлечено 15.12.2008
• Балог, Дж.; Регев, О.; Смит, К.; Штайгер, В.; Сегеди, М. (2004), «Длинные монотонные пути в линейных расположениях», Дискретная и вычислительная геометрия , 32 (2): 167–176, doi : 10.1007/s00454-004-1119-1
• Берн, М. В.; Эппштейн, Д .; Плассман, П. Е.; Яо, Ф. Ф. (1991), «Теоремы о горизонте для линий и многоугольников», в Goodman, Дж. Э .; Поллак, Р.; Штайгер, В. (ред.), Дискретная и вычислительная геометрия: статьи специального года DIMACS , DIMACS Ser. Discrete Math. and Theoretical Computer Science (6-е изд.), Amer. Math. Soc., стр. 45–66, MR  1143288
• Борвейн, П. ; Мозер, WOJ (1990), «Обзор проблемы Сильвестра и ее обобщений», Aequationes Mathematicae , 40 (1): 111–135, doi : 10.1007/BF02112289, MR  1069788, S2CID  122052678
• Бозе, П .; Эванс, В.; Киркпатрик, Д.Г.; МакАллистер, М.; Сноейинк, Дж. (1996), «Аппроксимация кратчайших путей в расположениях линий», Труды 8-й Канадской конференции по вычислительной геометрии , стр. 143–148
• de Bruijn, NG (1981), «Алгебраическая теория непериодических мозаик Пенроуза плоскости» (PDF) , Indagationes Mathematicae , 43 : 38–66, архивировано (PDF) из оригинала 2021-05-07 , извлечено 2024-10-16
• Кэнхэм, Р. Дж. (1969), «Теорема о расположении прямых на плоскости», Israel Journal of Mathematics , 7 (4): 393–397, doi : 10.1007/BF02788872 , S2CID  123541779
• Чан, Т. (1999), Замечания об алгоритмах k-уровня на плоскости, архивировано из оригинала 2010-11-04
• Шазелл, Б.; Гибас , Л. Дж.; Ли , Д. Т. (1985), «Сила геометрической дуальности», BIT Numerical Mathematics , 25 (1): 76–90, doi :10.1007/BF01934990, S2CID  122411548
• Кларксон, К.; Эдельсбруннер , Х.; Гибас , Л. Дж .; Шарир, М .; Вельцль, Э. (1990), «Оценки комбинаторной сложности для расположений кривых и сфер», Дискретная и вычислительная геометрия , 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- множеств и связанных с ними проблем», Дискретная и вычислительная геометрия , 19 (3): 373–382, doi : 10.1007/PL00009354 , MR  1608878
• Дирак, Г. (1951), «Свойства коллинеарности множеств точек», Quarterly Journal of Mathematics , 2 (1): 221–227, Bibcode : 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
• Эдельсбруннер, Х.; Гибас , Л. Дж. (1989), «Топологическая подметка расположения», Журнал компьютерных и системных наук , 38 (1): 165–194, doi : 10.1016/0022-0000(89)90038-X
• Эдельсбруннер, Х.; Гибас , Л. Дж.; Шарир , М. (1990), «Сложность и построение многих граней в расположениях линий и отрезков», Дискретная и вычислительная геометрия , 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, архивировано из оригинала 2012-02-14 , извлечено 2024-10-16
• Эппштейн, Д .; Фальмань, Ж.-Кл. ; Овчинников, С. (2007), Теория СМИ , Springer-Verlag.
• Эппштейн, Д.; Харт, Д. (1999), «Кратчайшие пути в расположении с k ориентациями линий», Труды 10-го симпозиума ACM–SIAM по дискретным алгоритмам (SODA '99) , стр. 310–316
• Erdős, P. ; Lovász, L. ; Simmons, A.; Straus, EG (1973), "Графы рассечения плоских точечных множеств", Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) , Амстердам: North-Holland, стр. 139–149, MR  0363986
• Эриксон, Дж. (1997), Кратчайшие пути в линейных расположениях, архивировано из оригинала 2008-12-03 , извлечено 2008-12-15
• Fortune, S.; Milenkovic, V. (1991), "Численная устойчивость алгоритмов для линейных расположений", Proc. 7th ACM Symposium on Computational Geometry (SoCG '91) , стр. 334–341, CiteSeerX  10.1.1.56.2404 , doi :10.1145/109648.109685, ISBN 978-0897914260, S2CID  2861855
• де Фрейссе, Х.; Оссона де Мендес, П. (2003), «Растяжение контактных систем дуг Жордана», Труды 11-го Международного симпозиума по рисованию графов (GD 2003) , Lecture Notes in Computer Science (2912 ed.), Springer-Verlag, стр. 71–85
• Füredi, Z. ; Palásti, I. (1984), "Расположение линий с большим количеством треугольников" (PDF) , Труды Американского математического общества , 92 (4): 561–566, doi :10.2307/2045427, JSTOR  2045427, архивировано из оригинала (PDF) 2016-03-03 , извлечено 2008-12-15
• Гудман, Якоб Э .; Поллак, Ричард (1993), «Допустимые последовательности и типы порядка в дискретной и вычислительной геометрии», в Pach, János (ред.), Новые тенденции в дискретной и вычислительной геометрии , алгоритмы и комбинаторика, т. 10, Берлин: Springer, стр. 103–134, doi :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), Arrangements and Spreads , Regional Conference Series in Mathematics, т. 10, Провиденс, Род-Айленд: Американское математическое общество
• Грюнбаум, Бранко (2009), «Каталог симплициальных расположений в реальной проективной плоскости», Ars Mathematica Contemporanea , 2 (1): 1–25, doi : 10.26493/1855-3974.88.e12 , hdl : 1773/2269 , MR  2485643
• Гальперин, Д.; Шарир, М. (2018), «Расположения», в Goodman, Jacob E.; O'Rourke, Joseph; Tóth, Csaba D. (ред.), Справочник по дискретной и вычислительной геометрии , Дискретная математика и ее приложения (3-е изд.), Бока-Ратон, Флорида: CRC Press, стр. 723–762, ISBN 978-1-4987-1139-5, г-н  3793131
• Келли, Л. М.; Мозер, В. О. Дж. (1958), «О числе обычных линий, определяемых n точками», Канадский математический журнал , 10 : 210–219, doi : 10.4153/CJM-1958-024-6
• Клее, Р. (1938), Über die einfachen Konfigurationen der euklidischen und der projektiven Ebene , Дрезден: Focken & Oltmanns
• Лейтон, Ф.Т. (1983), Проблемы сложности в СБИС , Серия «Основы вычислений», Кембридж, Массачусетс: Издательство MIT
• Леви, Ф. (1926), «Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade», Ber. Матем.-Физ. кл. Сакс. Акад. Висс. Лейпциг , 78 : 256–267.
• Ловас, Л. (1971), «О количестве делений пополам», Annales Universitatis Scientiarum Buddhainensis de Rolando Eőtvős Nominatae Sectio Mathematica , 14 : 107–108
• Мартин, Джордж Э. (1996), Основы геометрии и неевклидова плоскость , Бакалаврские тексты по математике, Springer-Verlag, ISBN 0-387-90694-0, МР  1410263
• Матоушек, Й. (1991), «Нижние оценки длины монотонных путей в конфигурациях», Дискретная и вычислительная геометрия , 6 (1): 129–134, doi : 10.1007/BF02574679
• Мельхиор, Э. (1940), «Über Vielseite der projektiven Ebene», Deutsche Mathematik , 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), «Elproblea de los triángulos de Kobon» [Проблема треугольников Кобона], La Gaceta de la Real Sociedad Matemática Española (на испанском языке), 24 (1): 111–130, hdl : 10486/705416, МР  4225268
• Овчинников, Сергей (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), «Треугольники в расположениях линий», Дискретная математика , 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), «Расположение линий с минимальным числом треугольников является простым», Дискретная и вычислительная геометрия , 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) из оригинала 2021-06-26 , извлечено 2024-10-16
• Shor, PW (1991), «Растяжимость псевдолиний — задача NP-трудная», в Gritzmann, P.; Sturmfels, B. (ред.), Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, т. 4, Providence, RI: American Mathematical Society, стр. 531–554
• Штайнер, Дж. (1826), «Einige Gesetze über die Theilung der Ebene und des Raumes», Дж. Рейн Ангью. Математика. , 1 : 349–364, doi : 10.1515/crll.1826.1.349, S2CID  120477563
• Штроммер, TO (1977), «Треугольники в расположениях линий», Журнал комбинаторной теории, Серия A , 23 (3): 314–320, doi : 10.1016/0097-3165(77)90022-X
• Székely, LA (1997), «Пересекающиеся числа и сложные проблемы Эрдёша в дискретной геометрии» (PDF) , Комбинаторика, вероятность и вычисления , 6 (3): 353–358, doi :10.1017/S0963548397002976, S2CID  36602807, заархивировано (PDF) из оригинала 2017-08-08 , извлечено 2024-10-16
• Tóth, G. (2001), «Точечные множества с множеством k -множеств», Discrete & Computational Geometry , 26 (2): 187–194, doi : 10.1007/s004540010022

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

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