Loading AI tools
розбиття площини, утворене набором прямих З Вікіпедії, вільної енциклопедії
Конфігурація прямих (або розбиття площини прямими)[1] — це розбиття площини, утворене набором прямих. Конфігурації прямих вивчає комбінаторна геометрія, а в обчислювальній геометрії будуються алгоритми для ефективної побудови конфігурацій.
Для будь-якої множини A прямих на евклідовій площині можна визначити відношення еквівалентності на точках площини, за яким дві точки p і q еквівалентні, якщо для будь-якої прямої l із A або p і q обидві лежать на прямій l, або вони лежать у тій самій відкритій півплощині, обмеженій прямою l. Якщо A скінченна або локально скінченна[2], класи еквівалентності цих відношень належать трьом групам:
Ці три типи об'єктів, з'єднані разом, утворюють клітинне розбиття, що покриває площину. Кажуть, що дві конфігурації прямих ізоморфні або комбінаторно еквівалентні, якщо існує відповідність між об'єктами в клітинних розбиттях, яке один-до-одного зберігає суміжність.[3]
Вивчення конфігурацій прямих почав Якоб Штейнер, який довів першу межу найбільшого числа елементів різних типів, яке може містити конфігурація[4][5]. Конфігурація з n прямих має не більше n (n − 1) / 2 вершин, по одній на пару перетинних прямих. Цей максимум досягається на простих конфігураціях. Конфігурація називається простою, якщо
У будь-якій конфігурації буде n нескінченних, спрямованих вниз променів, по одному на пряму. Ці промені відокремлюють n + 1 комірок розбиття, необмежених знизу. Решта комірок мають єдину найнижчу вершину,[6] і кожна така вершина є нижньою для єдиної комірки, так що число комірок розбиття дорівнює числу вершин плюс n + 1 або не перевищує n(n + 1)/2 + 1, див. Центральні багатокутні числа. Число ребер розбиття не перевищує n2, що можна побачити або за допомогою ейлерової характеристики, підставивши число вершин і комірок, або скориставшись спостереженням, що кожну пряму розділено максимум на n ребер іншими n − 1 прямими. Знову, гіршим випадком, на якому межа досягається, є прості конфігурації прямих.
Зона прямої l у наборі прямих — це набір комірок, які мають ребра, що лежать на l. Теорема про зону стверджує, що повне число ребер в осередках окремої зони лінійне. Точніше, повне число ребер комірок (із зони прямої), що містяться по один бік від прямої l, не більш як 5n − 1[7][8][9], а повне число ребер комірок, що лежать по обидва боки від l, не перевищує [10]. Загальніше, повна складність комірок розбиття, які перетинаються опуклою кривою, дорівнює O(n α(n)), де α позначає обернену функцію Аккермана, що можна показати, виходячи з послідовностей Девенпорта — Шінцеля[en][10]. Підсумовуючи складність усіх зон, можна виявити, що сума квадратів складностей комірок у розбитті дорівнює O(n2)[11].
k-рівень[en] конфігурації прямих — це ламана, утворена ребрами, які мають рівно k інших прямих під нею (тобто промінь, опущений вниз від ребра, перетинає рівно k прямих), а ≤k-рівень — це всі частини конфігурації прямих, що містяться під k-рівнем. Знаходження верхньої і нижньої меж складності для k-рівнів залишається головною відкритою проблемою дискретної геометрії. Кращою верхньою межею є O(nk1/3), тоді як кращою нижньою — Ω(n exp(c (logk)1/2)) [12][13][14]. Відомо, що максимальна складність ≤k-рівня дорівнює Θ(nk) [15]. k-рівень є окремим випадком монотонного шляху в розбитті площини, тобто послідовності ребер, які перетинають будь-яку вертикальну пряму в окремій точці. Однак монотонні шляхи можуть бути складнішими, ніж k-рівні — існують набори прямих і монотонні шляхи в цих наборах, де число точок, на яких шлях змінює напрямок, дорівнює Ω(n2 − o(1))[16].
Хоча окрема комірка в розбитті може бути обмежена всіма n прямими, неможливо в загальному випадку, щоб m різних комірок були обмежені n прямими. Навпаки, повна складність m комірок майже дорівнює Θ(m2/3n2/3 + n)[17][18] і майже така ж межа з'являється в теоремі Семереді — Троттера про інциденцію точок і прямих на площині. Просте доведення цього факту випливає з нерівності числа перетинів — якщо m комірок мають загалом x + n ребер, можна створити граф з m вершинами (по одній на комірку) і x ребрами (по одному на пару послідовних комірок на тій самій прямій)[19][20]. Ребра цього графа можна намалювати як криві, які не перетинаються всередині комірок, відповідних кінцевим вершинам ребер, а потім слідують по прямих набору. Отже, на цьому малюнку є O(n2) перетинів. Однак, за нерівністю числа перетинів, існує Ω(x3/m2) перетинів. Щоб виконувалися обидві нерівності, x має бути O(m2/3n2/3)[21].
Часто зручно вивчати конфігурацію прямих не в евклідовому просторі, а на проєктивній площині, оскільки в проєктивній геометрії будь-яка пара прямих має точку перетину. На проєктивній площині ми не можемо визначити розбиття з використанням боків прямих (пряма на проєктивній площині не ділить площину на два різні боки), але ми все ж можемо визначити комірки розбиття як зв'язні компоненти точок, які не лежать на жодній прямій. Ребрами будуть зв'язні компоненти, що складаються з множини точок, які належать окремій прямий, а вершинами будуть точки, де дві або більше прямих перетинаються. Набір прямих на проєктивній площині відрізняється від його евклідового двійника, оскільки два евклідових промені по обидва боки від прямої замінюються одним ребром на проєктивній площині, а пари необмежених евклідових комірок замінюються на проєктивній площині в єдині комірки.
З огляду на проєктивну двоїстість багато тверджень про комбінаторні властивості точок на площині можна легко зрозуміти в еквівалентній двоїстій формі про конфігурації прямих. Наприклад, теорема Сильвестра, яка стверджує, що будь-яка неколінеарна множина точок на площині має просту пряму, яка містить рівно дві точки, перетворюється за проєктивною двоїстістю на твердження, що будь-яка конфігурація прямих, яка має більше ніж одну вершину, має просту точку, вершину, в якій перетинаються всього дві прямі. Найраніше відоме доведення теореми Сильвестра Мельхіором (Melchior, (1940)) використовує ейлерову характеристику.
Конфігурацію прямих у проєктивній площині називають симпліційною, якщо будь-яка комірка розбиття обмежена рівно трьома ребрами. Симпліційні конфігурації першим вивчав Мельхіор[22][23]. Три нескінченних сімейства симпліційних наборів прямих відомі:
Крім того, є багато інших прикладів одиничних симпліційних конфігурацій, які не вміщаються в якесь відоме нескінченне сімейство[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° одне відносно одного (що формують тришестикутну мозаїку) побудова дає ромбічну мозаїку. Однак для більшого числа сімейств прямих ця побудова дає аперіодичні мозаїки. Зокрема, для п'яти сімейств прямих з рівними кутами одне відносно одного (або, як де Брейн називає цю конфігурацію, пентагріда) це дає сімейство замощень, яке включає ромбічну версію мозаїк Пенроуза.
Розділена квадратна мозаїка — це нескінченна конфігурація прямих, що утворює періодичне замощення, яке нагадує мультисітку з чотирма паралельними родинами, але в якій два сімейства мають більшу відстань між прямими, ніж в інших двох, і в яких набір прямих є симпліційним, а не простим. Двоїстою мозаїкою є зрізана квадратна мозаїка[ru]. Подібним чином, трикутний паркет є нескінченною симпліційною конфігурацією прямих з трьома сімействами паралельних прямих, у якій двоїстою мозаїкою є шестикутний паркет, а розділена шестикутна мозаїка[en] є нескінченною симпліційною конфігурацією прямих із шістьма сімействами паралельних прямих і двома відстанями між прямими в сімействах, яка двоїста великій ромботришестикутній мозаїці[en].
Конструювання конфігурації означає обчислення подання вершин, ребер і комірок конфігурації прямих (разом з їх взаємозв'язками) при заданні списку прямих у наборі, наприклад як у двозв'язному списку ребер. Згідно з теоремою про зони, набори можна побудувати ефективно за допомогою інкрементного алгоритму, який додає по одній прямій за крок до набору прямих, доданих на попередніх кроках — кожну нову пряму можна додати за час, пропорційний її зоні, що в результаті дає час O(n2)[7]. Однак вимоги до пам'яті в цьому алгоритмі високі, так що може бути зручнішим перерахування всіх властивостей конфігурації в алгоритмі, який не зберігає всю конфігурацію в пам'яті. Це можна зробити ефективно за час O(n2) і з пам'яттю O(n) за допомогою алгоритмічної техніки, відомої як топологічне вимітання[39]. Точне обчислення конфігурації прямих вимагає обчислювальної точності, в кілька разів більшої, ніж вхідні дані (координати) — якщо пряма задається двома точками на ній, координати конфігурації вершин можуть зажадати в 4 рази більшої точності, ніж точність точок вхідних даних. Тому в обчислювальній геометрії вивчають також алгоритми побудови конфігурацій ефективно з обмеженою чисельною точністю[40][41][42].
Також дослідники вивчали ефективні алгоритми побудови менших частин конфігурації, таких як зони[43], k-рівні[44][45][46][47] або множини комірок, що містять заданий набір точок[48][49][50]. Задача знаходження конфігурації вершин з медіаною x-координат виникає (в двоїстій формі) в робастних статистиках як задача обчислення оцінки Тейла — Сена множини точок[51].
Марк ван Кревельд запропонував алгоритмічну задачу обчислення найкоротшого шляху між вершинами в конфігурації прямих, де шляхи обмежені ребрами конфігурації. Задача ставиться так: чи є алгоритми, що працюють за час, менший ніж квадратичний, який знадобився б для алгоритму пошуку найкоротшого шляху в повному графі конфігурації[52]. Відомий апроксимаційний алгоритм[53], і задачу можна ефективно розв'язати для прямих, які розбиваються на невелике число сімейств паралельних прямих (що типово для вулиць міст)[54], однак задача в загальному вигляді залишається відкритою.
Конфігурація псевдопрямих — це конфігурація кривих, що мають схожі топологічні властивості зі конфігурацією прямих[24][55]. Їх найпростіше можна визначити на проєктивній площині як прості замкнуті криві, з яких будь-які дві перетинаються трансверсально в єдиній точці. Кажуть, що конфігурація псевдопрямих розтяжна, якщо вона комбінаторно еквівалентна конфігурації прямих. Задача відрізнення розтяжних наборів від нерозтяжних[56][57] є NP-повною. Будь-яку конфігурацію скінченного числа псевдопрямих можна розширити, так що псевдопрямі стають прямими в неевклідовій геометрії інцидентності, в якій будь-які дві точки топологічної площини з'єднані єдиною прямою (як на евклідовій площині), але в якій інші аксіоми евклідової геометрії можуть не виконуватися.
Нерозтяжний набір дев'яти псевдопрямих. (Усі набори з числом псевдопрямих менше дев'яти — розтяжні.) За теоремою Паппа цю конфігурацію не можна реалізувати в проєктивній площині над будь-яким полем. |
Гіперболічна конфігурація прямих комбінаторно еквівалентна діаграмі хорд, використаній Агеєвим[58] для доведення, що коловий граф без трикутників може іноді вимагати 5 кольорів. |
Іншим типом неевклідової геометрії є гіперболічна площина, і конфігурації гіперболічних прямих у цій геометрії також вивчалися. Будь-яка скінченна множина прямих на евклідовій площині має комбінаторно еквівалентну конфігурацію в гіперболічній площині (наприклад, укладаючи вершини набору у велике коло і інтерпретуючи його внутрішність як модель Кляйна гіперболічної площини). Однак у гіперболічному наборі прямих можна уникнути перетинання прямих без вимоги паралельності прямих. Граф перетинів прямих у гіперболічній конфігурації є коловим графом. Відповідне поняття гіперболічної конфігурації прямих для псевдопрямих — слабка конфігурація псевдопрямих[59], сімейство кривих, яке має ті ж топологічні властивості, що й прямі[60], такі, що будь-які дві криві в сімействі або перетинаються в одній точці, або не перетинаються взагалі.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
