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

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

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

Определение [ править ]

Для любого множества линий в евклидовой плоскости , можно определить отношение эквивалентности на точках плоскости в соответствии с которым две точки и эквивалентны , если для каждой строки из , либо и оба на или оба принадлежат к одной и той же открытой половине -самолет ограничен . Когда конечна или локально конечна ^[1] , что классы эквивалентности этого отношения бывают трех типов:${\ displaystyle A}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle \ ell}$${\ displaystyle A}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle \ ell}$${\ displaystyle \ ell}$${\ displaystyle A}$

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

Эти три типа объектов соединяются вместе, образуя комплекс ячеек, покрывающий плоскость. Два расположения называются изоморфными или комбинаторно эквивалентными, если существует взаимно однозначное соответствие, сохраняющее смежность между объектами в связанных с ними комплексах ячеек. ^[2]

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

Изучение аранжировок было начато Якобом Штайнером , который доказал первые границы максимального количества функций различных типов, которые может иметь аранжировка. ^[3] Расположение с линиями имеет не более чем вершин ( треугольное число ), по одной на пару пересекающихся линий. Этот максимум достигается для простых схем , в которых каждые две линии имеют отдельную пару точек пересечения. В любом расположении будут бесконечные лучи, направленные вниз, по одному на линию; эти лучи разделяют ячейки системы, неограниченные в направлении вниз. Все остальные ячейки имеют единственную самую нижнюю вершину, ^[4]${\ displaystyle n}$${\ Displaystyle п (п-1) / 2}$${\ displaystyle n}$${\ displaystyle n + 1}$и каждая вершина является самой нижней для уникальной ячейки, поэтому количество ячеек в расположении равно количеству вершин плюс , или самое большее ; см . последовательность ленивого кейтеринга . Число ребер в расположении не больше , что можно увидеть либо с использованием характеристики Эйлера для вычисления ее из числа вершин и ячеек, либо с учетом того, что каждая линия делится не более чем на ребра другими линиями; опять же, эта оценка наихудшего случая достигается для простых устройств.${\ displaystyle n + 1}$${\ Displaystyle п (п + 1) / 2 + 1}$${\ Displaystyle п ^ {2}}$${\ displaystyle n}$${\ displaystyle n-1}$

Зона линии в расположении линии представляет собой набор ячеек , имеющие ребро , принадлежащее . Теорема о зоне утверждает, что общее количество ребер в ячейках одной зоны линейно. Точнее, общее число ребер клеток , принадлежащих к одной стороне линии не более , ^[5] , а общее число ребер клеток , принадлежащих к обеим сторонам не больше . ^{[6] В} более общем смысле, общая сложность ячеек линейного расположения, которые пересекаются любой выпуклой кривой, составляет , где обозначает обратную функцию Аккермана , как можно показать с помощью${\ displaystyle \ ell}$${\ displaystyle \ ell}$${\ displaystyle \ ell}$${\ displaystyle 5n-1}$${\ displaystyle \ ell}$${\ displaystyle \ lfloor 9.5n \ rfloor -1}$${\ Displaystyle О (п \ альфа (п)}$${\ displaystyle \ alpha}$Последовательности Давенпорта – Шинцеля . ^[6] Суммируя сложность всех зон, можно найти, что сумма квадратов сложности ячеек в расположении равна . ^[7]${\ Displaystyle О (п ^ {2})}$

- уровень расположения является ломаным , образованными ребрами , которые имеют в точности других линий непосредственно под ними, а -уровень представляет собой часть устройства ниже -й. Нахождение совпадающих верхней и нижней границ сложности a -уровня остается большой открытой проблемой в дискретной геометрии; лучшая верхняя граница , а лучшая нижняя граница . ^[8] Напротив, максимальная сложность -уровня известна . ^[9] А${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle \ leq k}$${\ displaystyle k}$${\ displaystyle k}$${\ Displaystyle О (нк ^ {1/3})}$${\displaystyle n2^{\Omega ({\sqrt {\log k}})}}$${\displaystyle \leq k}$${\displaystyle \Theta (nk)}$${\displaystyle k}$-уровень - частный случай монотонной дорожки в расположении; то есть последовательность ребер, которая пересекает любую вертикальную линию в одной точке. Однако монотонные траектории могут быть намного сложнее, чем -уровни: в этих компоновках существуют компоновки и монотонные траектории, в которых количество точек, в которых траектория меняет направление, равно . ^[10]${\displaystyle k}$${\displaystyle n^{2-o(1)}}$

Хотя одна ячейка в расположении может быть ограничена всеми линиями, в целом невозможно, чтобы все разные ячейки были ограничены линиями. Скорее, общая сложность клеток составляет не более , ^[11] почти такой же связаны , как это происходит в теореме Семереди-Trotter на точку линии случаев в плоскости. Простое доказательство этого следует из неравенства числа пересечений : ^[12] если ячейки имеют всего ребер, можно сформировать граф с узлами (по одному на ячейку) и${\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}$ребра (по одному на пару последовательных ячеек на одной строке). Ребра этого графа могут быть нарисованы как кривые, которые не пересекаются внутри ячеек, соответствующих их конечным точкам, а затем следуют по линиям расположения; следовательно, на этом чертеже есть пересечения. Однако из-за неравенства числа пересечений пересечения бывают ; чтобы удовлетворить обе границы, должно быть . ^[13]${\displaystyle O(n^{2})}$${\displaystyle \Omega (x^{3}/m^{2})}$${\displaystyle x}$${\displaystyle O(m^{2/3}n^{2/3})}$

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

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

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

Треугольники в расположении [ править ]

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

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

Вдобавок есть много других примеров спорадических симплициальных расположений, которые не вписываются ни в одно известное бесконечное семейство. ^[15] Как пишет Грюнбаум ^[16] , симплициальные схемы «появляются как примеры или контрпримеры во многих контекстах комбинаторной геометрии и ее приложений». Например, Artés, Grünbaum & Llibre (1998) используют симплициальные схемы для построения контрпримеров к гипотезе о связи между степенью набора дифференциальных уравнений и количеством инвариантных прямых, которые могут иметь уравнения. Два известных контрпримера к гипотезе Дирака – Моцкина (которая гласит, что любая конфигурация -строчных линий имеет не менее${\displaystyle n}$${\displaystyle n/2}$обычные точки) обе симплициальны. ^[17]

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

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

Мультисетки и мозаики Пенроуза [ править ]

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

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

Алгоритмы [ править ]

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

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

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

Неевклидовы линии [ править ]

Расположение pseudoline представляет собой семейство кривых , которые имеют сходные топологические свойства с расположением линии. ^[32] Их проще всего определить на проективной плоскости как простые замкнутые кривые, любые две из которых пересекаются в одной точке пересечения. ^[33] Псевдолинейное расположение называется растяжимым, если оно комбинаторно эквивалентно линейному расположению; для экзистенциальной теории реальных вещей это завершено, чтобы отличить растяжимые структуры от нерастяжимых. ^[34]Любое расположение конечного числа псевдолинии может быть расширено так, что они станут линиями в «развороте», типе неевклидовой геометрии инцидентности, в которой каждые две точки топологической плоскости соединены единственной линией (как в евклидовой плоскости) но в котором другие аксиомы евклидовой геометрии могут не применяться.

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

См. Также [ править ]

• Конфигурация (геометрия) , расположение линий и набор точек, где все линии содержат одинаковое количество точек и все точки принадлежат одинаковому количеству линий.
• Компоновка (пространственное разделение) , разделение плоскости, заданной наложенными кривыми, или пространства более высокой размерности, наложенными поверхностями, без требования, чтобы кривые или поверхности были плоскими.
• K-множество (геометрия) , связанное проективной двойственностью с -уровнями в расположении линий.${\displaystyle k}$
• Математический мост , мост в Кембридже, Англия, балки которого образуют расположение касательных линий к его арке.

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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