Войти
Симплициальное расположение строк (слева) и простое расположение строк (справа). В геометрии структура строк - это раздел плоскости плоскости, образованный набором строк. Границы сложности схем были изучены в дискретной геометрии, а в вычислительных геометрах были найдены алгоритмы для эффективного построения схем.
Для любого набора A линий в евклидовой плоскости, можно определить отношение эквивалентности в точках плоскости, согласно которому две точки p и q эквивалентны, если для каждой прямой l из A либо p, либо q находятся на l, либо на обеих принадлежат одной открытой полуплоскости, ограниченной l. Когда A конечна или локально конечна, классы эквивалентности этого отношения делятся на три типа:
Эти три типа объекты соединяются вместе, образуя комплекс ячеек , покрывающий плоскость. Два расположения называются изоморфными или комбинаторно эквивалентными, если существует взаимно однозначное соответствие, сохраняющее смежность между объектами в связанных с ними комплексах клеток.
Изучение Аранжировки были начаты Якобом Штайнером, который доказал первые границы максимального количества функций различных типов, которые может иметь аранжировка. Компоновка с n линиями имеет не более n (n - 1) / 2 вершин, по одной на пару пересекающихся линий. Этот максимум достигается для простых схем, в которых каждые две линии имеют отдельную пару точек пересечения. В любом расположении будет n лучей, направленных вниз, по одному на линию; эти лучи разделяют n + 1 ячейку конструкции, неограниченную в направлении вниз. У всех остальных ячеек есть уникальная самая нижняя вершина, и каждая вершина является самой нижней для уникальной ячейки, поэтому количество ячеек в расположении равно количеству вершин плюс n + 1, или не более n (n + 1) / 2 + 1; см. последовательность ленивого поставщика услуг. Число ребер компоновки не превышает n, что можно увидеть, используя эйлерову характеристику для ее вычисления по количеству вершин и ячеек, или наблюдая, что каждая линия разбита не более чем на n ребер по остальным n - 1 линиям; опять же, эта оценка наихудшего случая достигается для простых устройств.
Зона линии l в линейном расположении - это совокупность ячеек, края которых принадлежат l. Утверждает, что общее количество ребер в ячейках одной зоны линейно. Точнее, общее количество ребер ячеек, принадлежащих одной стороне прямой l, не превышает 5n - 1, а общее количество ребер ячеек, принадлежащих обеим сторонам прямой l, не превышает 
k-уровень расположения - это многоугольная цепочка, образованная ребрами, которые имеют ровно k других линий непосредственно под ними, а ≤k-уровень - это часть расположения ниже k-уровня. Нахождение совпадающих верхней и нижней границ сложности k-уровня остается большой открытой проблемой в дискретной геометрии; наилучшая верхняя граница - O (nk), а наилучшая нижняя оценка - Ω (n exp (c (logk))). Напротив, максимальная сложность ≤k-уровня, как известно, равна Θ (nk). K-уровень - это частный случай монотонного пути в расположении; то есть последовательность ребер, которая пересекает любую вертикальную линию в одной точке. Однако монотонные пути могут быть намного сложнее, чем k-уровни: в этих схемах существуют схемы и монотонные пути, в которых количество точек, в которых путь меняет направление, равно Ω (n).
Хотя одна ячейка в расположении может быть ограничено всеми n линиями, в общем случае невозможно, чтобы все m различных ячеек были ограничены n линиями. Скорее общая сложность m ячеек не превосходит (mn + n), почти такая же граница, как в теореме Семереди – Троттера о падениях между точками на плоскости. Простое доказательство этого следует из неравенства числа пересечений : если m ячеек имеют в сумме x + n ребер, можно сформировать граф с m вершинами (по одному на ячейку) и x ребрам (по одному на пару последовательных ячеек на одной строке). Ребра этого графа могут быть нарисованы как кривые, которые не пересекаются внутри ячеек, соответствующих их конечным точкам, а затем следуют по линиям расположения; следовательно, на этом чертеже имеется O (n) переходов. Однако по неравенству числа пересечений существуют пересечения Ω (x / m); чтобы удовлетворить обеим границам, x должен быть O (mn).
Часто удобно изучать расположение линий не в евклидовой плоскости, а в проективная плоскость, потому что в проективной геометрии каждая пара прямых имеет точку пересечения. В проективной плоскости мы больше не можем определять конфигурации, используя стороны линий (линия в проективной плоскости не разделяет плоскость на две различные стороны), но мы все же можем определять ячейки как связанные компоненты точки, не принадлежащие ни одной прямой, ребра - это компоненты связности наборов точек, принадлежащих одной прямой, а вершины - это точки пересечения двух или более прямых. Расположение линий в проективной плоскости отличается от своего евклидова аналога тем, что два евклидовых луча на обоих концах линии заменяются одним ребром в проективной плоскости, которое соединяет крайнюю левую и крайнюю правую вершины на этой прямой, и в этих парах неограниченные евклидовы ячейки заменяются на проективной плоскости одиночными ячейками, которые пересекает проективная прямая на бесконечности.
Благодаря проективной двойственности, многие утверждения о комбинаторных свойствах точек на плоскости могут быть легче поняты в эквивалентной двойственной форме о расположении прямых. Например, теорема Сильвестра – Галла, утверждающая, что любое неколлинеарное множество точек на плоскости имеет обычную линию, содержащую ровно две точки, при проективной двойственности трансформируется в утверждение, что любое расположение прямых с более чем чем одна вершина имеет обычную точку, вершину, в которой пересекаются только две прямые. Самое раннее известное доказательство теоремы Сильвестра – Галла, сделанное Мельхиором (1940), использует эйлерову характеристику, чтобы показать, что такая вершина всегда должна существовать.
Треугольники Кобона в расположении 17 линий Расположение прямых на проективной плоскости называется симплициальным, если каждая ячейка расположения ограничена ровно тремя края; симплициальные устройства были впервые изучены Мельхиором. Известны три бесконечных семейства конфигураций симплициальных линий:
Кроме того, есть много других примеров спорадических симплициальных расположений, которые не вписываются ни в одну известную бесконечную семью. Как пишет Грюнбаум, симплициальные устройства «появляются как примеры или контрпримеры во многих контекстах комбинаторной геометрии и ее приложений». Например, Artés, Grünbaum Llibre (1998) используют симплициальные схемы для построения контрпримеров к гипотезе о связи между степенью набора дифференциальных уравнений и количеством инвариантных прямых. уравнения могут иметь. Два известных контрпримера к гипотезе Дирака – Моцкина (которая утверждает, что любое расположение n-линий имеет не менее n / 2 обычных точек) являются симплициальными.
Двойственный граф линейной компоновки, в которой есть один узел на ячейку и одно ребро, связывающее любую пару ячеек, которые разделяют ребро компоновки, представляет собой частичный куб, граф, в котором узлы могут быть помеченным битовыми векторами таким образом, чтобы расстояние графа равнялось расстоянию Хэмминга между метками; в случае расположения линий каждая координата маркировки присваивает 0 узлам на одной стороне одной из линий и 1 узлам на другой стороне. Двойственные графы симплициальных расположений использовались для построения бесконечных семейств 3-правильных частичных кубов, изоморфных графам простых зоноэдров.
. Также представляет интерес изучение экстремальных чисел треугольных ячейки в расположениях, которые не обязательно могут быть симплициальными. В любом расположении должно быть не менее n треугольников; каждая компоновка, состоящая только из n треугольников, должна быть простой. Максимально возможное количество треугольников в простом расположении, как известно, ограничено сверху значением n (n - 1) / 3 и ограничено снизу значением n (n - 3) / 3; нижняя оценка достигается некоторыми подмножествами диагоналей правильного 2n-угольника. Для непростых расположений максимальное количество треугольников аналогично, но более строго ограничено. Тесно связанная задача треугольника Кобона требует максимального количества неперекрывающихся конечных треугольников (не обязательно граней) в расположении на евклидовой плоскости; для некоторых, но не всех значений n возможны n (n - 2) / 3 треугольника.
разделенный пополам гексагональный мозаик.Двойной граф простого расположения линий может быть геометрически представлен как набор ромбов, по одному на вершину компоновки со сторонами, перпендикулярными линиям, пересекающимся в этой вершине. Эти ромбы могут быть соединены вместе, чтобы образовать мозаику выпуклого многоугольника в случае расположения конечного числа прямых или всей плоскости в случае локально конечного расположения с бесконечным числом прямых. де Брюйн (1981) исследовал особые случаи этой конструкции, в которых расположение линий состоит из k наборов равноотстоящих параллельных прямых. Для двух перпендикулярных семейств параллельных прямых эта конструкция просто дает знакомую квадратную мозаику плоскости, а для трех семейств линий, расположенных под углом 120 градусов друг к другу (которые сами образуют трехгексагональную мозаику ) это дает мозаику ромбов. Однако для большего количества семейств линий эта конструкция дает апериодические мозаики. В частности, для пяти семейств линий, расположенных под равными углами друг к другу (или, как де Брейн называет это расположение, пентагрид), он создает семейство мозаик, которое включает ромбическую версию мозаик Пенроуза.
квадратная мозаика тетракис представляет собой бесконечное расположение линий, образующих периодическую мозаику, которая напоминает многосетку с четырьмя параллельными семействами, но в которой два семейства расположены более широко, чем два других, и в котором расположение является симплициальным а не просто. Его двойным элементом является усеченный квадратный тайлинг. Точно так же треугольная мозаика представляет собой бесконечную симплициальную линейную структуру с тремя параллельными семействами, которая имеет в качестве двойника шестиугольную мозаику, а разделенная пополам шестиугольная мозаика является бесконечное расположение симплициальных линий с шестью параллельными семействами и двумя межстрочными интервалами, двойственное большой ромбитрихексагональной мозаике.
Построение расположения означает, что в качестве входных данных предоставляется список строк в расположении, вычисление представление вершин, ребер и ячеек компоновки вместе с примыканиями между этими объектами, например, как список двусвязных ребер. В соответствии с теоремой о зоне конструкции могут быть эффективно построены с помощью инкрементного алгоритма, который добавляет по одной строке за раз к расположению ранее добавленных линий: каждая новая линия может быть добавлена во времени, пропорциональном ее зоне, в результате чего общее время строительства из O (n). Однако требования к памяти этого алгоритма высоки, поэтому может быть удобнее сообщать обо всех особенностях компоновки с помощью алгоритма, который не сохраняет всю компоновку в памяти сразу. Это снова может быть выполнено эффективно за время O (n) и пространство O (n) с помощью алгоритмической техники , известной как топологическое сканирование. Точное вычисление расположения линий требует числовой точности, в несколько раз превышающей точность входных координат: если линия задана двумя точками на ней, координаты вершин расположения могут потребовать в четыре раза большей точности, чем эти входные точки. Таким образом, вычислительные геометры также изучали алгоритмы для эффективного построения схем с ограниченной числовой точностью.
Кроме того, исследователи изучали эффективные алгоритмы построения меньших частей схемы, таких как зоны, k-уровни или множество ячеек, содержащих заданный набор точек. Проблема нахождения вершины расположения со средней координатой x возникает (в двойственной форме) в робастной статистике как проблема вычисления оценки Тейла – Сена набора точек.
Марк ван Кревельд предложил алгоритмическую задачу вычисления кратчайших путей между вершинами в линейном расположении, где пути ограничены следовать за ребрами расположения, быстрее, чем квадратичное время. что потребуется для применения алгоритма кратчайшего пути ко всему графу расположения. Алгоритм аппроксимации известен, и проблема может быть эффективно решена для линий, которые попадают в небольшое количество параллельных семейств (что типично для городских уличных сетей), но общая проблема остается открытой.
Нерастяжимые псевдолинии из девяти псевдолиний. (Все расположения менее чем девяти псевдолинией могут быть растянуты.) Согласно теореме Паппа о шестиугольнике, такое расположение не может быть реализовано в проективной плоскости над любым полем. 
Гиперболическое расположение линий комбинаторно эквивалентно хордовой диаграмме, использованной Агеевым (1996), чтобы показать, что без треугольников круговых графиков иногда может потребоваться 5 цветов.A псевдолинейное расположение - это семейство кривых, которые имеют аналогичные топологические свойства с расположением линий. Их проще всего определить на проективной плоскости как простые замкнутые кривые, любые две из которых пересекаются в одной точке пересечения. Псевдолинейное расположение называется растяжимым, если оно комбинаторно эквивалентно линейному расположению; завершено для экзистенциальной теории вещественных чисел, чтобы отличить растягиваемые структуры от нерастяжимых. Любое расположение конечного числа псевдолинии может быть расширено так, что они станут линиями в «развороте», типе неевклидовой геометрии инцидентности, в которой каждые две точки топологической плоскости соединены единственной линией ( как в евклидовой плоскости), но в которой другие аксиомы евклидовой геометрии могут не применяться.
Другой тип неевклидовой геометрии - это гиперболическая плоскость, и расположение гиперболических линий в этой геометрии также было изучено. Любой конечный набор прямых на евклидовой плоскости имеет комбинаторно эквивалентное расположение в гиперболической плоскости (например, путем заключения вершин расположения в большой круг и интерпретации внутренней части круга как модели Клейна гиперболическая плоскость). Однако при гиперболическом расположении линий линии могут избегать пересечения друг друга, не будучи параллельными; граф пересечений прямых в гиперболическом расположении - это круговой граф. Соответствующее понятие для гиперболических линий для псевдолинии - это слабая псевдолинии, семейство кривых, имеющих те же топологические свойства, что и прямые, так что любые две кривые в семействе либо встречаются в одной точке пересечения, либо не имеют пересечения.
