Конфігурація прямих (або розбиття площини прямими)В англомовній літературі arrangement, що часто перекладають як конфігурація, однак існує інший термін configuration, який природно перекладати також словом конфігурація. Інколи використовують термін набір прямих, інколи — розбиття (прямими або гіперплощинами). — це розбиття площини, утворене набором прямих. Конфігурації прямих вивчає комбінаторна геометрія, а в обчислювальній геометрії будуються алгоритми для ефективної побудови конфігурацій.
Визначення Для будь-якої множини A прямих на евклідовій площині можна визначити відношення еквівалентності на точках площини, за яким дві точки p і q еквівалентні, якщо для будь-якої прямої l із A або p і q обидві лежать на прямій l, або вони лежать у тій самій відкритій півплощині, обмеженій прямою l. Якщо A скінченна або локально скінченнаУ локально скінченних наборах будь-яка обмежена підмножина площини може перетинатися лише скінченним числом прямих., класи еквівалентності цих відношень належать трьом групам:
внутрішності обмежених або необмежених опуклих многокутників (комірки розбиття) — зв'язні компоненти підмножини точок площини, що не містяться на жодній із прямих із A, відкриті відрізки і відкриті нескінченні промені (ребра розбиття) — зв'язні компоненти точок окремої прямої, що не належать ніякій іншій прямій із A, окремі точки (вершини розбиття) — перетин двох або більше прямих із A.
Ці три типи об'єктів, з'єднані разом, утворюють клітинне розбиття, що покриває площину. Кажуть, що дві конфігурації прямих ізоморфні або комбінаторно еквівалентні, якщо існує відповідність між об'єктами в клітинних розбиттях, яке один-до-одного зберігає суміжність.
Складність наборів Вивчення конфігурацій прямих почав Якоб Штейнер, який довів першу межу найбільшого числа елементів різних типів, яке може містити конфігурація. Конфігурація з n прямих має не більше n (n − 1) / 2 вершин, по одній на пару перетинних прямих. Цей максимум досягається на простих конфігураціях. Конфігурація називається простою, якщо
1. ніякі три прямі не перетинаються в одній точці 2. ніякі дві прямі не паралельні.
У будь-якій конфігурації буде n нескінченних, спрямованих вниз променів, по одному на пряму. Ці промені відокремлюють n + 1 комірок розбиття, необмежених знизу. Решта комірок мають єдину найнижчу вершину,Для комірок, у яких є горизонтальне нижнє ребро, вибираємо вершину праворуч. і кожна така вершина є нижньою для єдиної комірки, так що число комірок розбиття дорівнює числу вершин плюс n + 1 або не перевищує n(n + 1)/2 + 1, див. Центральні багатокутні числа. Число ребер розбиття не перевищує n2, що можна побачити або за допомогою ейлерової характеристики, підставивши число вершин і комірок, або скориставшись спостереженням, що кожну пряму розділено максимум на n ребер іншими n − 1 прямими. Знову, гіршим випадком, на якому межа досягається, є прості конфігурації прямих.
Зона прямої l у наборі прямих — це набір комірок, які мають ребра, що лежать на l. Теорема про зону стверджує, що повне число ребер в осередках окремої зони лінійне. Точніше, повне число ребер комірок (із зони прямої), що містяться по один бік від прямої l, не більш як 5n − 1, а повне число ребер комірок, що лежать по обидва боки від l, не перевищує . Загальніше, повна складність комірок розбиття, які перетинаються опуклою кривою, дорівнює O(n α(n)), де α позначає обернену функцію Аккермана, що можна показати, виходячи з . Підсумовуючи складність усіх зон, можна виявити, що сума квадратів складностей комірок у розбитті дорівнює O(n2).
конфігурації прямих — це ламана, утворена ребрами, які мають рівно k інших прямих під нею (тобто промінь, опущений вниз від ребра, перетинає рівно k прямих), а ≤k-рівень — це всі частини конфігурації прямих, що містяться під k-рівнем. Знаходження верхньої і нижньої меж складності для k-рівнів залишається головною відкритою проблемою дискретної геометрії. Кращою верхньою межею є O(nk1/3), тоді як кращою нижньою — Ω(n exp(c (logk)1/2)) Задачу обмеження складності k-рівнів уперше вивчали Ловаш () і група Ердеш, Сімонс, Страус ().. Відомо, що максимальна складність ≤k-рівня дорівнює Θ(nk) . k-рівень є окремим випадком монотонного шляху в розбитті площини, тобто послідовності ребер, які перетинають будь-яку вертикальну пряму в окремій точці. Однак монотонні шляхи можуть бути складнішими, ніж k-рівні — існують набори прямих і монотонні шляхи в цих наборах, де число точок, на яких шлях змінює напрямок, дорівнює Ω(n2 − o(1)); see also ..
Хоча окрема комірка в розбитті може бути обмежена всіма n прямими, неможливо в загальному випадку, щоб m різних комірок були обмежені n прямими. Навпаки, повна складність m комірок майже дорівнює Θ(m2/3n2/3 + n) і майже така ж межа з'являється в теоремі Семереді — Троттера про інциденцію точок і прямих на площині. Просте доведення цього факту випливає з нерівності числа перетинів — якщо m комірок мають загалом x + n ребер, можна створити граф з m вершинами (по одній на комірку) і x ребрами (по одному на пару послідовних комірок на тій самій прямій). Ребра цього графа можна намалювати як криві, які не перетинаються всередині комірок, відповідних кінцевим вершинам ребер, а потім слідують по прямих набору. Отже, на цьому малюнку є O(n2) перетинів. Однак, за нерівністю числа перетинів, існує Ω(x3/m2) перетинів. Щоб виконувалися обидві нерівності, x має бути O(m2/3n2/3).
Проєктивні конфігурації і проєктивна двоїстість Часто зручно вивчати конфігурацію прямих не в евклідовому просторі, а на проєктивній площині, оскільки в проєктивній геометрії будь-яка пара прямих має точку перетину. На проєктивній площині ми не можемо визначити розбиття з використанням боків прямих (пряма на проєктивній площині не ділить площину на два різні боки), але ми все ж можемо визначити комірки розбиття як зв'язні компоненти точок, які не лежать на жодній прямій. Ребрами будуть зв'язні компоненти, що складаються з множини точок, які належать окремій прямий, а вершинами будуть точки, де дві або більше прямих перетинаються. Набір прямих на проєктивній площині відрізняється від його евклідового двійника, оскільки два евклідових промені по обидва боки від прямої замінюються одним ребром на проєктивній площині, а пари необмежених евклідових комірок замінюються на проєктивній площині в єдині комірки.
З огляду на проєктивну двоїстість багато тверджень про комбінаторні властивості точок на площині можна легко зрозуміти в еквівалентній двоїстій формі про конфігурації прямих. Наприклад, теорема Сильвестра, яка стверджує, що будь-яка неколінеарна множина точок на площині має просту пряму, яка містить рівно дві точки, перетворюється за проєктивною двоїстістю на твердження, що будь-яка конфігурація прямих, яка має більше ніж одну вершину, має просту точку, вершину, в якій перетинаються всього дві прямі. Найраніше відоме доведення теореми Сильвестра Мельхіором () використовує ейлерову характеристику.
Трикутники в наборах прямих Конфігурацію прямих у проєктивній площині називають симпліційною, якщо будь-яка комірка розбиття обмежена рівно трьома ребрами. Симпліційні конфігурації першим вивчав Мельхіор. Три нескінченних сімейства симпліційних наборів прямих відомі:
Майже-пучок складається з n − 1 прямих, що проходять через одну точку, і однієї прямої, яка через цю точку не проходить, Сімейство прямих, утворених сторонами правильного многокутника разом з осями симетрії Сторони і осі симетрії парного правильного многокутника, разом із прямою на нескінченності.
Крім того, є багато інших прикладів одиничних симпліційних конфігурацій, які не вміщаються в якесь відоме нескінченне сімейство. Як пише Ґрюнбаум, симпліційні набори прямих «з'являються як приклади або контрприклади в багатьох контекстах комбінаторної геометрії і її застосувань». Наприклад, Артьє, Ґрюнбаум і Ллібре використовували симпліційні набори прямих для побудови контрприкладів до гіпотези про зв'язок між степенями набору диференціальних рівнянь і числом інваріантних прямих, які рівняння можуть мати. Обидва відомих контрприклади до гіпотези Дірака-Моцкіна (яка стверджує, що будь-яка конфігурація n прямих має щонайменше n/2 простих точок) — симпліційні.
Двоїстим графом конфігурації прямих, у якій існує одна вершина для комірки і одне ребро, що з'єднує вершини, відповідні коміркам із спільним ребром у конфігурації, є частковий куб, граф, у якому вершини можна позначити бітовими векторами так, що відстань на графі дорівнює відстані Геммінга між позначками. У разі конфігурацій прямих кожна координата набуває значення 0 для ребер по один бік від прямої і 1 для ребер по інший бік. Двоїсті графи симпліційних конфігурацій використовувалися для побудови нескінченних сімейств 3-регулярних часткових кубів, ізоморфних графам простого зоноедра.
Цікаво також вивчити екстремальні кількості трикутних комірок у конфігурації, яка не обов'язково симпліційна. У будь-якій конфігурації має бути щонайменше n трикутників. Будь-яка конфігурація, що має тільки n трикутників, має бути простою. Відомо, що найбільше можливе число трикутників у простій конфігурації обмежене зверху числом n(n − 1)/3, а нижня межа дорівнює n(n − 3)/3. Нижня межа досягається на деяких підмножинах діагоналей правильного 2n-кутника. Для непростих конфігурацій найбільше число трикутників схоже, але сильніше обмежене. У тісно пов'язаній задачі Кобона про трикутники запитується про найбільшу кількість неперекривних скінченних трикутників (не обов'язково граней) у конфігурації на евклідовій площині. Для деяких, але не для всіх значень n, можливо n(n − 2)/3 трикутників.
Мультисіткові мозаїки і мозаїки Пенроуза
Двоїстий граф простої конфігурації прямих можна подати геометрично як набір ромбів, по одному на вершину конфігурації зі сторонами, перпендикулярними до прямих, які перетинаються у вершині. Ці ромби можна об'єднати з утворенням замощення опуклого многокутника в разі конфігурації скінченного числа прямих або всієї площини в разі локально скінченних конфігурацій з нескінченним числом прямих. Де Брейн досліджував окремі випадки цієї побудови, в яких конфігурація прямих складається з k множин паралельних прямих з рівним віддаленням одна від одної. Для двох перпендикулярних сімейств паралельних прямих ця побудова дає квадратний паркет на площині, а для трьох сімейств прямих під кутом 120° одне відносно одного (що формують тришестикутну мозаїку) побудова дає ромбічну мозаїку. Однак для більшого числа сімейств прямих ця побудова дає аперіодичні мозаїки. Зокрема, для п'яти сімейств прямих з рівними кутами одне відносно одного (або, як де Брейн називає цю конфігурацію, пентагріда) це дає сімейство замощень, яке включає ромбічну версію мозаїк Пенроуза.
Розділена квадратна мозаїка — це нескінченна конфігурація прямих, що утворює періодичне замощення, яке нагадує мультисітку з чотирма паралельними родинами, але в якій два сімейства мають більшу відстань між прямими, ніж в інших двох, і в яких набір прямих є симпліційним, а не простим. Двоїстою мозаїкою є . Подібним чином, трикутний паркет є нескінченною симпліційною конфігурацією прямих з трьома сімействами паралельних прямих, у якій двоїстою мозаїкою є шестикутний паркет, а є нескінченною симпліційною конфігурацією прямих із шістьма сімействами паралельних прямих і двома відстанями між прямими в сімействах, яка двоїста .
Алгоритми