Конфигурация (астрономия)
- 1 year ago
- 0
- 0
Конфигура́ция прямы́х (или разбие́ние пло́скости прямы́ми ) — это разбиение плоскости , образованное набором прямых . Конфигурации прямых изучается в комбинаторной геометрии , а в вычислительной геометрии строятся алгоритмы для эффективного построения конфигураций.
Для любого множества 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 2 , что можно видеть либо с помощью эйлеровой характеристики , подставив число вершин и ячеек, либо используя наблюдение, что каждая прямая разделена максимум на n рёбер другими n − 1 прямыми. Снова, худшим случаем, на котором граница достигается, являются простые конфигурации прямых.
Зона прямой l в наборе прямых — это набор ячеек, имеющих рёбра, лежащие на l . Теорема о зоне утверждает, что полное число рёбер в ячейках отдельной зоны линейно. Точнее, полное число рёбер ячеек (из зоны прямой), находящихся по одной стороне прямой l , не больше 5 n − 1 , а полное число рёбер ячеек, лежащих по обе стороны от l , не превосходит . Более обще, полная сложность ячеек разбиения, которые пересекаются выпуклой кривой, равна O( n α( n )), где α обозначает обратную функцию Аккермана , что можно показать, исходя из . Суммируя сложность всех зон, можно обнаружить, что сумма квадратов сложностей ячеек в разбиении равна O( n 2 ) .
конфигурации прямых — это ломаная , образованная рёбрами, которые имеют в точности k других прямых под ней (то есть луч, опущенный вниз от ребра, пересекает в точности k прямых), а ≤k-уровень — это все части конфигурации прямых, находящиеся под k -уровнем. Нахождение верхней и нижней границ сложности для k -уровней остаётся главной открытой проблемой дискретной геометрии. Лучшей верхней границей является O( nk 1/3 ), в то время как лучшей нижней — Ω( n exp( c (log k ) 1/2 )) . Известно, что максимальная сложность ≤ k -уровня равна Θ( nk ) . k -уровень является специальным случаем монотонного пути в разбиении плоскости, то есть последовательности рёбер, пересекающих любую вертикальную прямую в отдельной точке. Однако монотонные пути могут быть сложнее, чем k -уровни — существуют наборы прямых и монотонные пути в этих наборах, где число точек, на которых путь меняет направление, равно Ω( n 2 − o(1) ) .
Хотя отдельная ячейка в разбиении может быть ограничена всеми n прямыми, невозможно в общем случае, чтобы m различных ячеек были ограничены n прямыми. Наоборот, полная сложность m ячеек почти равна Θ( m 2/3 n 2/3 + n ) и почти та же самая граница появляется в об инциденции точек и прямых на плоскости. Простое доказательство этого факта следует из неравенства числа пересечений — если m ячеек имеют в общем счёте x + n рёбер, можно создать граф с m вершинами (по одной на ячейку) и x рёбрами (по одному на пару последовательных ячеек на той же самой прямой) . Рёбра этого графа можно нарисовать как кривые, которые не пересекаются внутри ячеек, соответствующих конечным вершинам рёбер, а затем следуют по прямым набора. Таким образом, имеется O( n 2 ) пересечений на этом рисунке. Однако, по неравенству числа пересечений, существует Ω( x 3 / m 2 ) пересечений. Чтобы выполнялись оба неравенства, x должен быть O( m 2/3 n 2/3 ) .
Часто удобно изучать конфигурацию прямых не в евклидовом пространстве, а на проективной плоскости , поскольку в проективной геометрии любая пара прямых имеет точку пересечения. На проективной плоскости мы не можем определить разбиение с использованием сторон прямых (прямая на проективной плоскости не разделяет плоскость на две различные стороны), но мы, всё же, можем определить ячейки разбиения как связные компоненты точек, не лежащих ни на какой прямой. Рёбрами будут связные компоненты, состоящие из множеств точек, принадлежащих отдельной прямой, а вершинами будут точки, где две или больше прямых пересекаются. Набор прямых на проективной плоскости отличается от его евклидового двойника, поскольку два евклидовых луча по обеим сторонам прямой заменяются одним ребром на проективной плоскости, а пары неограниченных евклидовых ячеек заменяются на проективной плоскости в единые ячейки.
Ввиду проективной двойственности многие утверждения о комбинаторных свойствах точек на плоскости могут быть более просто поняты в эквивалентной двойственной форме о конфигурациях прямых. Например, теорема Сильвестра , утверждающая, что любое неколлинеарное множество точек на плоскости имеет простую прямую , содержащая ровно две точки, превращается по проективной двойственности в утверждение, что любая конфигурация прямых, имеющая более одной вершины, имеет простую точку , вершину, в которой пересекаются всего две прямые. Наиболее раннее известное доказательство теоремы Сильвестра Мельхиором ( ) использует эйлерову характеристику .
Говорят, что конфигурация прямых в проективной плоскости является симплициальной , если любая ячейка разбиения ограничена в точности тремя рёбрами. Симплициальные конфигурации первым изучал Мельхиор . Три бесконечных семейства симплициальных наборов прямых известны:
Кроме того, имеется много других примеров единичных симплициальных конфигураций , которые не вмещаются в какое-либо известное бесконечное семейство . Как пишет Грюнбаум , симплициальные наборы прямых «появляются в качестве примеров или контрпримеров во многих контекстах комбинаторной геометрии и её приложений». Например, Артье, Грюнбаум и Ллибре использовали симплициальные наборы прямых для построения контрпримеров гипотезе о связи между степенями набора дифференциальных уравнений и числом инвариантных прямых, которые уравнения могут иметь. Два известных контрпримера гипотезе Дирака-Моцкина (которая утверждает, что любая конфигурация n прямых имеет по меньшей мере n /2 простых точек) оба симплициальны .
Двойственным графом конфигурации прямых, в которой существует одна вершина для ячейки и одно ребро, соединяющее вершины, соответствующие ячейкам с общим ребром в конфигурации, является частичный куб , граф, в котором вершины можно пометить битовыми векторами таким образом, что расстояние на графе равно расстоянию Хэмминга между метками. В случае конфигураций прямых каждая координата принимает значение 0 для рёбер с одной стороны прямой и 1 для рёбер с другой стороны . Двойственные графы симплициальных конфигураций использовались для построения бесконечных семейств 3-регулярных частичных кубов, изоморфных графам простого зоноэдра .
Интересно также изучить экстремальные количества треугольных ячеек в конфигурации, которая не обязательно симплициальна. В любой конфигурации должно быть по меньшей мере n треугольников. Любая конфигурация, имеющая только n треугольников, должна быть простой . Известно, что максимальное возможное число треугольников в простой конфигурации ограничена сверху числом n ( n − 1)/3, а минимальная граница равна n ( n − 3)/3. Нижняя граница достигается на некоторых подмножествах диагоналей правильного 2 n -угольника . Для непростых конфигураций максимальное число треугольников похоже, но более сильно ограничено . Тесно связанная задача Кобона о треугольниках спрашивает о максимальном числе неперекрывающихся конечных треугольников (не обязательно граней) в конфигурации на евклидовой плоскости. Для некоторых, но не для всех значений n , возможно n ( n − 2)/3 треугольников.
Двойственный граф простой конфигурации прямых можно представить геометрически как набор ромбов , по одному на вершину конфигурации со сторонами, перпендикулярными прямым, которые пересекаются в вершине. Эти ромбы могут быть объединены с образованием замощения выпуклого многоугольника в случае конфигурации конечного числа прямых или всей плоскости в случае локально конечных конфигураций с бесконечным числом прямых. Де Брёйн исследовал специальные случаи этого построения, в которых конфигурация прямых состоит из k множеств параллельных прямых с равным отстоянием друг от друга. Для двух перпендикулярных семейств параллельных прямых это построение просто даёт знакомый квадратный паркет на плоскости, а для трёх семейств прямых под углом 120 градусов по отношению друг к другу (тем самым формирующие тришестиугольную мозаику ) построение даёт ромбическую мозаику . Однако для большего числа семейств прямых это построение даёт апериодичные мозаики . В частности, для пяти семейств прямых с равными углами друг к другу (или, как де Брёйн называет эту конфигурацию, пентагрида ) это даёт семейство замощений, которое включает ромбическую версию мозаик Пенроуза .
Разделённая квадратная мозаика — это бесконечная конфигурация прямых, образующая периодическое замощение, которое напоминает мультисетку с четырьмя параллельными семействами, но в которой два семейства имеют большее расстояние между прямыми, чем в других двух, и в которых набор прямых является симплициальным, а не простым. Двойственной мозаикой является усечённая квадратная мозаика . Подобным образом, треугольный паркет является бесконечной симплициальной конфигурацией прямых с тремя семействами параллельных прямых, у которой двойственной мозаикой является шестиугольный паркет , а является бесконечной симплициальной конфигурацией прямых с шестью семействами параллельных прямых и двумя расстояниями между прямыми в семействах, которая двойственна .
Конструирование конфигурации означает вычисление представления вершин, рёбер и ячеек конфигурации прямых (вместе с их взаимосвязями) при задании списка прямых в наборе, например как в двусвязном списке рёбер . Согласно теореме о зонах, наборы можно построить эффективно с помощью инкрементного алгоритма, который добавляет по одной прямой за шаг к набору прямых, добавленных на предыдущих шагах — каждая новая прямая может быть добавлена за время, пропорциональное её зоне, что в результате даёт время O( n 2 ) . Однако требования к памяти в этом алгоритме высоки, так что может быть более удобным перечисление всех свойств конфигурации в алгоритме, не сохраняющем всю конфигурации в памяти. Это можно сделать эффективно за время O( n 2 ) и с памятью O( n ) с помощью алгоритмической техники, известной как топологическое выметание . Точное вычисление конфигурации прямых требует вычислительную точность, в несколько раз большую, чем входные данные (координаты) — если прямая задаётся двумя точками на ней, координаты конфигурации вершин могут потребовать в четыре раза большую точность, чем точность точек входных данных. Поэтому в вычислительной геометрии изучают также алгоритмы построения конфигураций эффективно с ограниченной численной точностью .
Также исследователи изучали эффективные алгоритмы построения меньших частей конфигурации, таких как зоны , k -уровни или множества ячеек, содержащих заданный набор точек . Задача нахождения конфигурации вершин с медианой x -координат возникает (в двойственной форме) в робастных статистиках как задача вычисления оценки Тейла — Сена множества точек .
Марк ван Кревельд предложил алгоритмическую задачу вычисления кратчайшего пути между вершинами в конфигурации прямых, где пути ограничены рёбрам конфигурации. Задача ставится так: есть ли алгоритмы, работающие за время, меньшее чем квадратичное, которое потратил бы алгоритм поиска кратчайшего пути в полном графе конфигурации . Известен аппроксимационный алгоритм , и задача может быть эффективно решена для прямых, которые разбиваются на небольшое число семейств параллельных прямых (что типично для улиц городов) , однако задача в общем виде остаётся открытой.
Конфигурация псевдопрямых — это конфигурация кривых , имеющих похожие топологические свойства с конфигурацией прямых . Их наиболее просто можно определить на проективной плоскости как простые замкнутые кривые, из которых любые две пересекаются трансверсально в единственной точке. Говорят, что конфигурация псевдопрямых растяжима , если онa комбинаторно эквивалентен конфигурации прямых. Задача отличения выпрямляемых наборов от невыпрямляемых является NP-полной . Любая конфигурация конечного числа псевдопрямых может быть расширена, так что псевдопрямые становятся прямыми в неевклидовой геометрии инцидентности , в которой любые две точки топологической плоскости соединены единственной прямой (как на евклидовой плоскости), но в которой другие аксиомы евклидовой геометрии могут не выполняться.
Нерастяжимый набор девяти псевдопрямых. (Все наборы с числом псевдопрямых меньше девяти выпрямляемы.) По теореме Паппа эта конфигурация не может быть реализована в проективной плоскости над любым полем. |
Гиперболическая конфигурация прямых комбинаторно эквивалентна диаграмме хорд, использованной Агеевым для доказательства, что круговой граф без треугольников может иногда требовать пять цветов . |
Другим типом неевклидовой геометрии является плоскость Лобачевского , и конфигурации гиперболических прямых в этой геометрии также изучались. Любое конечное множество прямых на евклидовой плоскости имеет комбинаторно эквивалентную конфигурацию в гиперболической плоскости (например, заключая вершины набора в большой круг и интерпретируя внутренность цикла как модель Клейна гиперболической плоскости). Однако в гиперболическом наборе прямых можно избежать пересечения прямых без требования параллельности прямых. Граф пересечений прямых в гиперболической конфигурации является круговым графом . Соответствующее понятие гиперболической конфигурации прямых для псевдопрямых — слабая конфигурация псевдопрямых , семейство кривых, имеющее те же топологические свойства, что и прямые , такие, что любые две кривые в семействе либо пересекаются в одной точке, либо не пересекаются вообще.