Русская Википедия:Конфигурация прямых

Симплициальная конфигурация прямых (слева) и простая конфигурация прямых (справа).

Конфигура́ция прямы́х (или разбие́ние пло́скости прямы́ми)^[1] — это разбиение плоскости, образованное набором прямых. Конфигурации прямых изучается в комбинаторной геометрии, а в вычислительной геометрии строятся алгоритмы для эффективного построения конфигураций.

Определение

Для любого множества A прямых на евклидовой плоскости можно определить отношение эквивалентности на точках плоскости, по которому две точки p и q эквивалентны, если для любой прямой l из A либо p и q обе лежат на прямой l, либо они лежат в той же самой открытой полуплоскости, ограниченной прямой l. Если A конечна или локально конечна^[2], классы эквивалентности этих отношений принадлежат трём группам:

внутренности ограниченных или неограниченных выпуклых многоугольников (ячейки разбиения), связные компоненты подмножества точек плоскости, не содержащихся ни на какой из прямых из A,
открытые отрезки и открытые бесконечные лучи (рёбра разбиения), связные компоненты точек отдельной прямой, не принадлежащие никакой другой прямой из A,
отдельные точки (вершины разбиения), пересечение двух или более прямых из A.

Эти три типа объектов, соединённые вместе, образуют клеточное разбиение, покрывающее плоскость. Говорят, что две конфигурации прямых изоморфны или комбинаторно эквивалентны, если существует один-в-один сохраняющее смежность соответствие между объектами в клеточных разбиенияхШаблон:Sfn

Сложность наборов

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

1. никакие три прямые не пересекаются в одной точке

2. никакие две прямые не параллельны.

В любой конфигурации будет n бесконечных, направленных вниз лучей, по одному на прямую. Эти лучи отделяют n + 1 ячеек разбиения, неограниченных снизу. Все оставшиеся ячейки имеют единственную самую нижнюю вершину,^[3] и каждая такая вершина является нижней для единственной ячейки, так что число ячеек разбиения равно числу вершин плюс n + 1 или не превосходит n(n + 1)/2 + 1, см. центральные многоугольные числа. Число рёбер разбиения не превосходит n², что можно видеть либо с помощью эйлеровой характеристики, подставив число вершин и ячеек, либо используя наблюдение, что каждая прямая разделена максимум на n рёбер другими n − 1 прямыми. Снова, худшим случаем, на котором граница достигается, являются простые конфигурации прямых.

Шаблон:Anchor Зона прямой l в наборе прямых — это набор ячеек, имеющих рёбра, лежащие на l. Теорема о зоне утверждает, что полное число рёбер в ячейках отдельной зоны линейно. Точнее, полное число рёбер ячеек (из зоны прямой), находящихся по одной стороне прямой l, не больше 5n − 1Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn, а полное число рёбер ячеек, лежащих по обе стороны от l, не превосходит <math>\lfloor 9.5n\rfloor-1</math>Шаблон:Sfn. Более обще, полная сложность ячеек разбиения, которые пересекаются выпуклой кривой, равна O(n α(n)), где α обозначает обратную функцию Аккермана, что можно показать, исходя из Шаблон:Iw Шаблон:Sfn. Суммируя сложность всех зон, можно обнаружить, что сумма квадратов сложностей ячеек в разбиении равна O(n²)Шаблон:Sfn.

Шаблон:Iw конфигурации прямых — это ломаная, образованная рёбрами, которые имеют в точности k других прямых под ней (то есть луч, опущенный вниз от ребра, пересекает в точности k прямых), а ≤k-уровень — это все части конфигурации прямых, находящиеся под k-уровнем. Нахождение верхней и нижней границ сложности для k-уровней остаётся главной открытой проблемой дискретной геометрии. Лучшей верхней границей является O(nk^1/3), в то время как лучшей нижней — Ω(n exp(c (logk)^1/2))Шаблон:Sfn Шаблон:Sfn^[4]. Известно, что максимальная сложность ≤k-уровня равна Θ(nk)Шаблон:Sfn. k-уровень является специальным случаем монотонного пути в разбиении плоскости, то есть последовательности рёбер, пересекающих любую вертикальную прямую в отдельной точке. Однако монотонные пути могут быть сложнее, чем k-уровни — существуют наборы прямых и монотонные пути в этих наборах, где число точек, на которых путь меняет направление, равно Ω(n^2 − o(1))Шаблон:Sfn Шаблон:Sfn.

Хотя отдельная ячейка в разбиении может быть ограничена всеми n прямыми, невозможно в общем случае, чтобы m различных ячеек были ограничены n прямыми. Наоборот, полная сложность m ячеек почти равна Θ(m^2/3n^2/3 + n)Шаблон:Sfn Шаблон:Sfn и почти та же самая граница появляется в Шаблон:Iw об инциденции точек и прямых на плоскости. Простое доказательство этого факта следует из неравенства числа пересечений — если m ячеек имеют в общем счёте x + n рёбер, можно создать граф с m вершинами (по одной на ячейку) и x рёбрами (по одному на пару последовательных ячеек на той же самой прямой)Шаблон:Sfn Шаблон:Sfn. Рёбра этого графа можно нарисовать как кривые, которые не пересекаются внутри ячеек, соответствующих конечным вершинам рёбер, а затем следуют по прямым набора. Таким образом, имеется O(n²) пересечений на этом рисунке. Однако, по неравенству числа пересечений, существует Ω(x³/m²) пересечений. Чтобы выполнялись оба неравенства, x должен быть O(m^2/3n^2/3)Шаблон:Sfn.

Проективные конфигурации и проективная двойственность

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

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

Треугольники в наборах прямых

Говорят, что конфигурация прямых в проективной плоскости является симплициальной, если любая ячейка разбиения ограничена в точности тремя рёбрами. Симплициальные конфигурации первым изучал МельхиорШаблон:Sfn Шаблон:Sfn. Три бесконечных семейства симплициальных наборов прямых известны:

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

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

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

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

Мультисеточные мозаики и мозаики Пенроуза

Файл:Tiling Dual Semiregular V4-6-12 Bisected Hexagonal.svg

Шаблон:Iw.

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

Разделённая квадратная мозаика — это бесконечная конфигурация прямых, образующая периодическое замощение, которое напоминает мультисетку с четырьмя параллельными семействами, но в которой два семейства имеют большее расстояние между прямыми, чем в других двух, и в которых набор прямых является симплициальным, а не простым. Двойственной мозаикой является усечённая квадратная мозаика. Подобным образом, треугольный паркет является бесконечной симплициальной конфигурацией прямых с тремя семействами параллельных прямых, у которой двойственной мозаикой является шестиугольный паркет, а Шаблон:Iw является бесконечной симплициальной конфигурацией прямых с шестью семействами параллельных прямых и двумя расстояниями между прямыми в семействах, которая двойственна Шаблон:Iw.

Алгоритмы

Конструирование конфигурации означает вычисление представления вершин, рёбер и ячеек конфигурации прямых (вместе с их взаимосвязями) при задании списка прямых в наборе, например как в двусвязном списке рёбер. Согласно теореме о зонах, наборы можно построить эффективно с помощью инкрементного алгоритма, который добавляет по одной прямой за шаг к набору прямых, добавленных на предыдущих шагах — каждая новая прямая может быть добавлена за время, пропорциональное её зоне, что в результате даёт время O(n²)Шаблон:Sfn. Однако требования к памяти в этом алгоритме высоки, так что может быть более удобным перечисление всех свойств конфигурации в алгоритме, не сохраняющем всю конфигурации в памяти. Это можно сделать эффективно за время O(n²) и с памятью O(n) с помощью алгоритмической техники, известной как топологическое выметаниеШаблон:Sfn. Точное вычисление конфигурации прямых требует вычислительную точность, в несколько раз большую, чем входные данные (координаты) — если прямая задаётся двумя точками на ней, координаты конфигурации вершин могут потребовать в четыре раза большую точность, чем точность точек входных данных. Поэтому в вычислительной геометрии изучают также алгоритмы построения конфигураций эффективно с ограниченной численной точностьюШаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

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

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

Вариации и обобщения

Конфигурация псевдопрямых

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

Файл:Pappos pseudo.svg Нерастяжимый набор девяти псевдопрямых. (Все наборы с числом псевдопрямых меньше девяти выпрямляемы.) По теореме Паппа эта конфигурация не может быть реализована в проективной плоскости над любым полем.	Файл:Ageev 5X circle graph.svg Гиперболическая конфигурация прямых комбинаторно эквивалентна диаграмме хорд, использованной АгеевымШаблон:Sfn для доказательства, что круговой граф без треугольников может иногда требовать пять цветов.

Плоскость Лобачевского

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

См. также

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Database of Combinatorially Different Line Arrangements

Шаблон:Rq

↑ В англоязычной литературе аrrangement, что часто переводится как конфигура́ция, однако существует другой термин configuration, который естественно переводить тоже словом конфигура́ция. Иногда используется термин набо́р прямы́х, иногда — разбие́ние (прямыми или гиперплоскостями).
↑ В локально конечных наборах любое ограниченное подмножество плоскости может пересекаться лишь конечным числом прямых.
↑ Для ячеек, в которых имеется горизонтальное нижнее ребро, выбираем вершину справа.
↑ Задачу ограничения сложности k-уровней впервые изучали Ловаш (Шаблон:Harvtxt) и группой Эрдёш, Симонс, Страус (Шаблон:Harvtxt).
↑ Альтернативное определение Шора Шаблон:Harvtxt — псевдопрямая является образом прямой гомеоморфизма плоскости.

[1] В англоязычной литературе аrrangement, что часто переводится как конфигура́ция, однако существует другой термин configuration, который естественно переводить тоже словом конфигура́ция. Иногда используется термин набо́р прямы́х, иногда — разбие́ние (прямыми или гиперплоскостями).

[2] В локально конечных наборах любое ограниченное подмножество плоскости может пересекаться лишь конечным числом прямых.

[3] Для ячеек, в которых имеется горизонтальное нижнее ребро, выбираем вершину справа.

[4] Задачу ограничения сложности k-уровней впервые изучали Ловаш (Шаблон:Harvtxt) и группой Эрдёш, Симонс, Страус (Шаблон:Harvtxt).

[5] Альтернативное определение Шора Шаблон:Harvtxt — псевдопрямая является образом прямой гомеоморфизма плоскости.

[1]

[2]

[3]

[4]

[5]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.