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

Матеріал з testwiki
Версія від 00:48, 11 вересня 2024, створена imported>Leonst
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)
Перейти до навігації Перейти до пошуку
Симпліційна конфігурація прямих (ліворуч) і проста конфігурація прямих (праворуч).

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

Визначення

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

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

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

Складність наборів

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

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

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

Зона прямої l у наборі прямих — це набір комірок, які мають ребра, що лежать на l. Теорема про зону стверджує, що повне число ребер в осередках окремої зони лінійне. Точніше, повне число ребер комірок (із зони прямої), що містяться по один бік від прямої l, не більш як 5n − 1Шаблон:SfnШаблон:SfnШаблон:Sfn, а повне число ребер комірок, що лежать по обидва боки від l, не перевищує ⌊9.5n⌋−1Шаблон:Sfn. Загальніше, повна складність комірок розбиття, які перетинаються опуклою кривою, дорівнює O(n α(n)), де α позначає обернену функцію Аккермана, що можна показати, виходячи з Шаблон:Не перекладеноШаблон:Sfn. Підсумовуючи складність усіх зон, можна виявити, що сума квадратів складностей комірок у розбитті дорівнює O(n2)Шаблон:Sfn.

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

Хоча окрема комірка в розбитті може бути обмежена всіма n прямими, неможливо в загальному випадку, щоб m різних комірок були обмежені n прямими. Навпаки, повна складність m комірок майже дорівнює Θ(m2/3n2/3 + n)Шаблон:SfnШаблон:Sfn і майже така ж межа з'являється в теоремі Семереді — Троттера про інциденцію точок і прямих на площині. Просте доведення цього факту випливає з нерівності числа перетинів — якщо m комірок мають загалом x + n ребер, можна створити граф з m вершинами (по одній на комірку) і x ребрами (по одному на пару послідовних комірок на тій самій прямій)Шаблон:SfnШаблон:Sfn. Ребра цього графа можна намалювати як криві, які не перетинаються всередині комірок, відповідних кінцевим вершинам ребер, а потім слідують по прямих набору. Отже, на цьому малюнку є O(n2) перетинів. Однак, за нерівністю числа перетинів, існує Ω(x3/m2) перетинів. Щоб виконувалися обидві нерівності, x має бути O(m2/3n2/3)Шаблон:Sfn.

Проєктивні конфігурації і проєктивна двоїстість

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

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

Трикутники в наборах прямих

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

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

Крім того, є багато інших прикладів одиничних симпліційних конфігурацій, які не вміщаються в якесь відоме нескінченне сімействоШаблон: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 трикутників.

Мультисіткові мозаїки і мозаїки Пенроуза

Шаблон:Не перекладено.

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

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

Алгоритми

Конструювання конфігурації означає обчислення подання вершин, ребер і комірок конфігурації прямих (разом з їх взаємозв'язками) при заданні списку прямих у наборі, наприклад як у двозв'язному списку ребер. Згідно з теоремою про зони, набори можна побудувати ефективно за допомогою інкрементного алгоритму, який додає по одній прямій за крок до набору прямих, доданих на попередніх кроках — кожну нову пряму можна додати за час, пропорційний її зоні, що в результаті дає час O(n2)Шаблон:Sfn. Однак вимоги до пам'яті в цьому алгоритмі високі, так що може бути зручнішим перерахування всіх властивостей конфігурації в алгоритмі, який не зберігає всю конфігурацію в пам'яті. Це можна зробити ефективно за час O(n2) і з пам'яттю O(n) за допомогою алгоритмічної техніки, відомої як топологічне вимітанняШаблон:Sfn. Точне обчислення конфігурації прямих вимагає обчислювальної точності, в кілька разів більшої, ніж вхідні дані (координати) — якщо пряма задається двома точками на ній, координати конфігурації вершин можуть зажадати в 4 рази більшої точності, ніж точність точок вхідних даних. Тому в обчислювальній геометрії вивчають також алгоритми побудови конфігурацій ефективно з обмеженою чисельною точністюШаблон:SfnШаблон:SfnШаблон:Sfn.

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

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

Варіації та узагальнення

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

Конфігурація псевдопрямих — це конфігурація кривих, що мають схожі топологічні властивості зі конфігурацією прямихШаблон:SfnШаблон:Sfn. Їх найпростіше можна визначити на проєктивній площині як прості замкнуті криві, з яких будь-які дві перетинаються трансверсально в єдиній точці. Кажуть, що конфігурація псевдопрямих розтяжна, якщо вона комбінаторно еквівалентна конфігурації прямих. Задача відрізнення розтяжних наборів від нерозтяжнихШаблон:SfnШаблон:Sfn є NP-повною. Будь-яку конфігурацію скінченного числа псевдопрямих можна розширити, так що псевдопрямі стають прямими в неевклідовій геометрії інцидентності, в якій будь-які дві точки топологічної площини з'єднані єдиною прямою (як на евклідовій площині), але в якій інші аксіоми евклідової геометрії можуть не виконуватися.

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

Гіперболічна конфігурація прямих комбінаторно еквівалентна діаграмі хорд, використаній АгеєвимШаблон:Sfn для доведення, що коловий граф без трикутників може іноді вимагати 5 кольорів.

Гіперболічна площина

Іншим типом неевклідової геометрії є гіперболічна площина, і конфігурації гіперболічних прямих у цій геометрії також вивчалися. Будь-яка скінченна множина прямих на евклідовій площині має комбінаторно еквівалентну конфігурацію в гіперболічній площині (наприклад, укладаючи вершини набору у велике коло і інтерпретуючи його внутрішність як модель Кляйна гіперболічної площини). Однак у гіперболічному наборі прямих можна уникнути перетинання прямих без вимоги паралельності прямих. Граф перетинів прямих у гіперболічній конфігурації є коловим графом. Відповідне поняття гіперболічної конфігурації прямих для псевдопрямих — слабка конфігурація псевдопрямихШаблон:Sfn, сімейство кривих, яке має ті ж топологічні властивості, що й прямі[6], такі, що будь-які дві криві в сімействі або перетинаються в одній точці, або не перетинаються взагалі.

Див. також

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

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

Посилання

  1. ↑ В англомовній літературі arrangement, що часто перекладають як конфігурація, однак існує інший термін configuration, який природно перекладати також словом конфігурація. Інколи використовують термін набір прямих, інколи — розбиття (прямими або гіперплощинами).
  2. ↑ У локально скінченних наборах будь-яка обмежена підмножина площини може перетинатися лише скінченним числом прямих.
  3. ↑ Для комірок, у яких є горизонтальне нижнє ребро, вибираємо вершину праворуч.
  4. ↑ Задачу обмеження складності k-рівнів уперше вивчали Ловаш (Шаблон:Harvtxt) і група Ердеш, Сімонс, Страус (Шаблон:Harvtxt).
  5. ↑ Шаблон:Harvtxt; see also Шаблон:Harvtxt.
  6. ↑ Альтернативне визначення Шора (Шаблон:Harvtxt) — псевдопряма є образом прямої гомеоморфізму площини.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Конфігурація_прямих&oldid=9130