Конфігурація прямих

Для будь-якої множини A прямих на евклідовій площині можна визначити відношення еквівалентності на точках площини, за яким дві точки p і q еквівалентні, якщо для будь-якої прямої l із A або p і q обидві лежать на прямій l, або вони лежать у тій самій відкритій півплощині, обмеженій прямою l. Якщо A скінченна або локально скінченна[2], класи еквівалентності цих відношень належать трьом групам:

1. внутрішності обмежених або необмежених опуклих многокутників (комірки розбиття) — зв'язні компоненти підмножини точок площини, що не містяться на жодній із прямих із A,
2. відкриті відрізки і відкриті нескінченні промені (ребра розбиття) — зв'язні компоненти точок окремої прямої, що не належать ніякій іншій прямій із A,
3. окремі точки (вершини розбиття) — перетин двох або більше прямих із A.

Ці три типи об'єктів, з'єднані разом, утворюють клітинне розбиття, що покриває площину. Кажуть, що дві конфігурації прямих ізоморфні або комбінаторно еквівалентні, якщо існує відповідність між об'єктами в клітинних розбиттях, яке один-до-одного зберігає суміжність.[3]

Вивчення конфігурацій прямих почав Якоб Штейнер, який довів першу межу найбільшого числа елементів різних типів, яке може містити конфігурація[4][5]. Конфігурація з n прямих має не більше n (n − 1) / 2 вершин, по одній на пару перетинних прямих. Цей максимум досягається на простих конфігураціях. Конфігурація називається простою, якщо

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

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

У будь-якій конфігурації буде n нескінченних, спрямованих вниз променів, по одному на пряму. Ці промені відокремлюють n + 1 комірок розбиття, необмежених знизу. Решта комірок мають єдину найнижчу вершину,[6] і кожна така вершина є нижньою для єдиної комірки, так що число комірок розбиття дорівнює числу вершин плюс n + 1 або не перевищує n(n + 1)/2 + 1, див. Центральні багатокутні числа. Число ребер розбиття не перевищує n^2, що можна побачити або за допомогою ейлерової характеристики, підставивши число вершин і комірок, або скориставшись спостереженням, що кожну пряму розділено максимум на n ребер іншими n − 1 прямими. Знову, гіршим випадком, на якому межа досягається, є прості конфігурації прямих.

Зона прямої l у наборі прямих — це набір комірок, які мають ребра, що лежать на l. Теорема про зону стверджує, що повне число ребер в осередках окремої зони лінійне. Точніше, повне число ребер комірок (із зони прямої), що містяться по один бік від прямої l, не більш як 5n − 1[7][8][9], а повне число ребер комірок, що лежать по обидва боки від l, не перевищує ${\displaystyle \lfloor 9.5n\rfloor -1}$[10]. Загальніше, повна складність комірок розбиття, які перетинаються опуклою кривою, дорівнює O(n α(n)), де α позначає обернену функцію Аккермана, що можна показати, виходячи з послідовностей Девенпорта — Шінцеля[10]. Підсумовуючи складність усіх зон, можна виявити, що сума квадратів складностей комірок у розбитті дорівнює O(n²)[11].

k-рівень конфігурації прямих — це ламана, утворена ребрами, які мають рівно k інших прямих під нею (тобто промінь, опущений вниз від ребра, перетинає рівно k прямих), а ≤k-рівень — це всі частини конфігурації прямих, що містяться під k-рівнем. Знаходження верхньої і нижньої меж складності для k-рівнів залишається головною відкритою проблемою дискретної геометрії. Кращою верхньою межею є O(nk^1/3), тоді як кращою нижньою — Ω(n exp(c (logk)^1/2)) [12][13][14]. Відомо, що максимальна складність ≤k-рівня дорівнює Θ(nk) [15]. k-рівень є окремим випадком монотонного шляху в розбитті площини, тобто послідовності ребер, які перетинають будь-яку вертикальну пряму в окремій точці. Однак монотонні шляхи можуть бути складнішими, ніж k-рівні — існують набори прямих і монотонні шляхи в цих наборах, де число точок, на яких шлях змінює напрямок, дорівнює Ω(n^2 − o(1))[16].

Хоча окрема комірка в розбитті може бути обмежена всіма n прямими, неможливо в загальному випадку, щоб m різних комірок були обмежені n прямими. Навпаки, повна складність m комірок майже дорівнює Θ(m^2/3n^2/3 + n)[17][18] і майже така ж межа з'являється в теоремі Семереді — Троттера про інциденцію точок і прямих на площині. Просте доведення цього факту випливає з нерівності числа перетинів — якщо m комірок мають загалом x + n ребер, можна створити граф з m вершинами (по одній на комірку) і x ребрами (по одному на пару послідовних комірок на тій самій прямій)[19][20]. Ребра цього графа можна намалювати як криві, які не перетинаються всередині комірок, відповідних кінцевим вершинам ребер, а потім слідують по прямих набору. Отже, на цьому малюнку є O(n²) перетинів. Однак, за нерівністю числа перетинів, існує Ω(x³/m²) перетинів. Щоб виконувалися обидві нерівності, x має бути O(m^2/3n^2/3)[21].

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

З огляду на проєктивну двоїстість багато тверджень про комбінаторні властивості точок на площині можна легко зрозуміти в еквівалентній двоїстій формі про конфігурації прямих. Наприклад, теорема Сильвестра, яка стверджує, що будь-яка неколінеарна множина точок на площині має просту пряму, яка містить рівно дві точки, перетворюється за проєктивною двоїстістю на твердження, що будь-яка конфігурація прямих, яка має більше ніж одну вершину, має просту точку, вершину, в якій перетинаються всього дві прямі. Найраніше відоме доведення теореми Сильвестра Мельхіором (Melchior, (1940)) використовує ейлерову характеристику.

Конфігурацію прямих у проєктивній площині називають симпліціальною, якщо будь-яка комірка розбиття обмежена рівно трьома ребрами. Симпліціальні конфігурації першим вивчав Мельхіор[22][23]. Три нескінченних сімейства симпліціальних наборів прямих відомі:

1. Майже-пучок складається з n − 1 прямих, що проходять через одну точку, і однієї прямої, яка через цю точку не проходить,
2. Сімейство прямих, утворених сторонами правильного многокутника разом з осями симетрії
3. Сторони і осі симетрії парного правильного многокутника, разом із прямою на нескінченності.

Крім того, є багато інших прикладів одиничних симпліціальних конфігурацій, які не вміщаються в якесь відоме нескінченне сімейство[24][23]. Як пише Ґрюнбаум[23], симпліціальні набори прямих «з'являються як приклади або контрприклади в багатьох контекстах комбінаторної геометрії і її застосувань». Наприклад, Артьє, Ґрюнбаум і Ллібре[25] використовували симпліціальні набори прямих для побудови контрприкладів до гіпотези про зв'язок між степенями набору диференціальних рівнянь і числом інваріантних прямих, які рівняння можуть мати. Обидва відомих контрприклади до гіпотези Дірака-Моцкіна (яка стверджує, що будь-яка конфігурація n прямих має щонайменше n/2 простих точок) — симпліціальні[26][27][28][29].

Двоїстим графом конфігурації прямих, у якій існує одна вершина для комірки і одне ребро, що з'єднує вершини, відповідні коміркам із спільним ребром у конфігурації, є частковий куб, граф, у якому вершини можна позначити бітовими векторами так, що відстань на графі дорівнює відстані Геммінга між позначками. У разі конфігурацій прямих кожна координата набуває значення 0 для ребер по один бік від прямої і 1 для ребер по інший бік[30]. Двоїсті графи симпліціальних конфігурацій використовувалися для побудови нескінченних сімейств 3-регулярних часткових кубів, ізоморфних графам простого зоноедра[31].

Цікаво також вивчити екстремальні кількості трикутних комірок у конфігурації, яка не обов'язково симпліціальна. У будь-якій конфігурації має бути щонайменше n трикутників. Будь-яка конфігурація, що має тільки n трикутників, має бути простою[24][32][33]. Відомо, що найбільше можливе число трикутників у простій конфігурації обмежене зверху числом n(n − 1)/3, а нижня межа дорівнює n(n − 3)/3. Нижня межа досягається на деяких підмножинах діагоналей правильного 2n-кутника[34][24]. Для непростих конфігурацій найбільше число трикутників схоже, але сильніше обмежене[35][36][37]. У тісно пов'язаній задачі Кобона про трикутники запитується про найбільшу кількість неперекривних скінченних трикутників (не обов'язково граней) у конфігурації на евклідовій площині. Для деяких, але не для всіх значень n, можливо n(n − 2)/3 трикутників.

Розділена шестикутна мозаїка.

Двоїстий граф простої конфігурації прямих можна подати геометрично як набір ромбів, по одному на вершину конфігурації зі сторонами, перпендикулярними до прямих, які перетинаються у вершині. Ці ромби можна об'єднати з утворенням замощення опуклого многокутника в разі конфігурації скінченного числа прямих або всієї площини в разі локально скінченних конфігурацій з нескінченним числом прямих. Де Брейн[38] досліджував окремі випадки цієї побудови, в яких конфігурація прямих складається з k множин паралельних прямих з рівним віддаленням одна від одної. Для двох перпендикулярних сімейств паралельних прямих ця побудова дає квадратний паркет на площині, а для трьох сімейств прямих під кутом 120° одне відносно одного (що формують тришестикутну мозаїку) побудова дає ромбічну мозаїку. Однак для більшого числа сімейств прямих ця побудова дає аперіодичні мозаїки. Зокрема, для п'яти сімейств прямих з рівними кутами одне відносно одного (або, як де Брейн називає цю конфігурацію, пентагріда) це дає сімейство замощень, яке включає ромбічну версію мозаїк Пенроуза.

Розділена квадратна мозаїка — це нескінченна конфігурація прямих, що утворює періодичне замощення, яке нагадує мультисітку з чотирма паралельними родинами, але в якій два сімейства мають більшу відстань між прямими, ніж в інших двох, і в яких набір прямих є симпліціальним, а не простим. Двоїстою мозаїкою є зрізана квадратна мозаїка. Подібним чином, трикутний паркет є нескінченною симпліціальною конфігурацією прямих з трьома сімействами паралельних прямих, у якій двоїстою мозаїкою є шестикутний паркет, а розділена шестикутна мозаїка є нескінченною симпліціальною конфігурацією прямих із шістьма сімействами паралельних прямих і двома відстанями між прямими в сімействах, яка двоїста великій ромботришестикутній мозаїці.

Конструювання конфігурації означає обчислення подання вершин, ребер і комірок конфігурації прямих (разом з їх взаємозв'язками) при заданні списку прямих у наборі, наприклад як у двозв'язному списку ребер. Згідно з теоремою про зони, набори можна побудувати ефективно за допомогою інкрементного алгоритму, який додає по одній прямій за крок до набору прямих, доданих на попередніх кроках — кожну нову пряму можна додати за час, пропорційний її зоні, що в результаті дає час O(n²)[7]. Однак вимоги до пам'яті в цьому алгоритмі високі, так що може бути зручнішим перерахування всіх властивостей конфігурації в алгоритмі, який не зберігає всю конфігурацію в пам'яті. Це можна зробити ефективно за час O(n²) і з пам'яттю O(n) за допомогою алгоритмічної техніки, відомої як топологічне вимітання[39]. Точне обчислення конфігурації прямих вимагає обчислювальної точності, в кілька разів більшої, ніж вхідні дані (координати) — якщо пряма задається двома точками на ній, координати конфігурації вершин можуть зажадати в 4 рази більшої точності, ніж точність точок вхідних даних. Тому в обчислювальній геометрії вивчають також алгоритми побудови конфігурацій ефективно з обмеженою чисельною точністю[40][41][42].

Також дослідники вивчали ефективні алгоритми побудови менших частин конфігурації, таких як зони[43], k-рівні[44][45][46][47] або множини комірок, що містять заданий набір точок[48][49][50]. Задача знаходження конфігурації вершин з медіаною x-координат виникає (в двоїстій формі) в робастних статистиках як задача обчислення оцінки Тейла — Сена множини точок[51].

Марк ван Кревельд запропонував алгоритмічну задачу обчислення найкоротшого шляху між вершинами в конфігурації прямих, де шляхи обмежені ребрами конфігурації. Задача ставиться так: чи є алгоритми, що працюють за час, менший ніж квадратичний, який знадобився б для алгоритму пошуку найкоротшого шляху в повному графі конфігурації[52]. Відомий апроксимаційний алгоритм[53], і задачу можна ефективно розв'язати для прямих, які розбиваються на невелике число сімейств паралельних прямих (що типово для вулиць міст)[54], однак задача в загальному вигляді залишається відкритою.

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

• Database of Combinatorially Different Line Arrangements