Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Конфігурація прямих або розбиття площини прямими це розбиття площини утворене набором прямих Конфігурації прямих вивчає

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

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

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

image
Симпліційна конфігурація прямих (ліворуч) і проста конфігурація прямих (праворуч).

Визначення

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

  1. внутрішності обмежених або необмежених опуклих многокутників (комірки розбиття) — зв'язні компоненти підмножини точок площини, що не містяться на жодній із прямих із A,
  2. відкриті відрізки і відкриті нескінченні промені (ребра розбиття) — зв'язні компоненти точок окремої прямої, що не належать ніякій іншій прямій із A,
  3. окремі точки (вершини розбиття) — перетин двох або більше прямих із 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, не перевищує image. Загальніше, повна складність комірок розбиття, які перетинаються опуклою кривою, дорівнює O(n α(n)), де α позначає обернену функцію Аккермана, що можна показати, виходячи з [en]. Підсумовуючи складність усіх зон, можна виявити, що сума квадратів складностей комірок у розбитті дорівнює O(n2).

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

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

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

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

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

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

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

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

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

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

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

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

image
[en].

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

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

Алгоритми

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

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

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

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

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

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

image

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

image

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

Площина Лобачевського

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

Див. також

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

Примітки

  1. В англомовній літературі arrangement, що часто перекладають як конфігурація, однак існує інший термін configuration, який природно перекладати також словом конфігурація. Інколи використовують термін набір прямих, інколи — розбиття (прямими або гіперплощинами).
  2. У локально скінченних наборах будь-яка обмежена підмножина площини може перетинатися лише скінченним числом прямих.
  3. Grünbaum, 1972, с. 4.
  4. Steiner, 1826.
  5. Agarwal, Sharir, 2000.
  6. Для комірок, у яких є горизонтальне нижнє ребро, вибираємо вершину праворуч.
  7. Chazelle et al, 1985.
  8. Edelsbrunner, 1987.
  9. Edelsbrunner, O'Rourke, Seidel, 1986.
  10. Bern, Eppstein, Plassman, Yao, 1991.
  11. Aronov, Matoušek, Sharir, 1994.
  12. Dey, 1998.
  13. Tóth, 2001.
  14. Задачу обмеження складності k-рівнів уперше вивчали Ловаш (Lovász, (1971)) і група Ердеш, Сімонс, Страус (Erdős et al, (1973)).
  15. Alon, Győri, 1986.
  16. Balogh та ін., (2004); see also Matoušek, (1991).
  17. Canham, 1969.
  18. Clarkson et al, 1990.
  19. Ajtai, Chvátal, Newborn, Szemerédi, 1982.
  20. Leighton, 1983.
  21. Székely, 1997.
  22. Melchior, 1940.
  23. Grünbaum, 2005.
  24. Grünbaum, 1972.
  25. Artés, Grünbaum, Llibre, 1998.
  26. Crowe, McKee, 1968.
  27. Dirac, 1951.
  28. Kelly, Moser, 1958.
  29. Grünbaum, 1972, с. 18.
  30. Eppstein, Falmagne, Ovchinnikov, 2007.
  31. Eppstein, 2006.
  32. Levi, 1926.
  33. Roudneff, 1988.
  34. Füredi, Palásti, 1984.
  35. Purdy, 1979.
  36. Purdy, 1980.
  37. Strommer, 1977.
  38. de Bruijn, 1981.
  39. Edelsbrunner, Guibas, 1989.
  40. Fortune, Milenkovic, 1991.
  41. Greene, Yao, 1986.
  42. Milenkovic, 1989.
  43. Aharoni et al, 1999.
  44. Agarwal, de Berg, Matoušek, Schwarzkopf, 1998.
  45. Chan, 1999.
  46. Cole, Sharir, Yap, 1987.
  47. Edelsbrunner, Welzl, 1986.
  48. Agarwal, 1990.
  49. Agarwal, Matoušek, Sharir, 1998.
  50. Edelsbrunner, Guibas, Sharir, 1990.
  51. Cole, Salowe, Steiger, Szemerédi, 1989.
  52. Erickson, 1997.
  53. Bose et al, 1996.
  54. Eppstein, Hart, 1999.
  55. Agarwal, Sharir, 2002.
  56. Shor, 1991.
  57. Schaefer, 2010.
  58. Ageev, 1996.
  59. de Fraysseix, Ossona de Mendez, 2003.
  60. Альтернативне визначення Шора (Shor, (1991)) — псевдопряма є образом прямої гомеоморфізму площини.

Література

  • P. K. Agarwal. Partitioning arrangements of lines II: Applications // . — 1990. — Т. 5, вип. 1. — С. 533–573. — DOI:10.1007/BF02187809.
  • P. K. Agarwal, M. de Berg, J. Matoušek, O. Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams // SIAM Journal on Computing. — 1998. — Т. 27, вип. 3. — С. 654–667. — DOI:10.1137/S0097539795281840.
  • P. K. Agarwal, J. Matoušek, M. Sharir. Computing many faces in arrangements of lines and segments // SIAM Journal on Computing. — 1998. — Т. 27, вип. 2. — С. 491–505. — DOI:10.1137/S009753979426616X.
  • P. K. Agarwal, M. Sharir. [1] — Elsevier, 2000. — С. 49–119. з джерела 10 червня 2007
  • P. K. Agarwal, M. Sharir. Proc. 13th ACM-SIAM Symp. Discrete algorithms (SODA '02). — San Francisco : Society for Industrial and Applied Mathematics, 2002. — С. 800–809.
  • A. A. Ageev. A triangle-free circle graph with chromatic number 5 // Discrete Math.. — 1996. — Т. 152. — С. 295–298. — DOI:10.1016/0012-365X(95)00349-2.
  • Y. Aharoni, D. Halperin, I. Hanniel, S. Har-Peled, C. Linhart. Proc. 3rd Int. Worksh. Algorithm Engineering (WAE '99). — Springer-Verlag, 1999. — Т. 1668. — С. 139–153. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-48318-7_13.
  • M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi. Theory and Practice of Combinatorics. — North-Holland, 1982. — Т. 60. — С. 9–12. — (North-Holland Mathematics Studies)
  • N. Alon, E. Győri. The number of small semi-spaces of a finite set of points in the plane // Journal of Combinatorial Theory, Series A. — 1986. — Т. 41. — С. 154–157. — DOI:10.1016/0097-3165(86)90122-6.
  • B. Aronov, J. Matoušek, M. Sharir. On the sum of squares of cell complexities in hyperplane arrangements // Journal of Combinatorial Theory, Series A. — 1994. — Т. 65, вип. 2. — С. 311–321. — DOI:10.1016/0097-3165(94)90027-2.
  • J. C. Artés, B. Grünbaum, J. Llibre. On the number of invariant straight lines for polynomial differential systems // Pacific Journal of Mathematics. — 1998. — Т. 184, вип. 2. — С. 207–230. — DOI:10.2140/pjm.1998.184.207. з джерела 18 липня 2010. Процитовано 26 червня 2021.
  • J. Balogh, O. Regev, C. Smyth, W. Steiger, M. Szegedy. Long monotone paths in line arrangements // . — 2004. — Т. 32, вип. 2. — С. 167–176. — DOI:10.1007/s00454-004-1119-1.
  • M. W. Bern, D. Eppstein, P. E. Plassman, F. F. Yao. Discrete and Computational Geometry: Papers from the DIMACS Special Year / J. E. Goodman, R. Pollack, W. Steiger. — Amer. Math. Soc, 1991. — С. 45–66. — (DIMACS Ser. Discrete Math. and Theoretical Computer Science)
  • P. Bose, W. Evans, D. G. Kirkpatrick, M. McAllister, J. Snoeyink. Proc. 8th Canadian Conf. Computational Geometry. — 1996. — С. 143–148.
  • N. G. de Bruijn. [2] — . — 1981. — Т. 43. — С. 38–66. з джерела 7 травня 2021
  • R. Canham. A theorem on arrangements of lines in the plane // Israel J. Math.. — 1969. — Т. 7, вип. 4. — С. 393–397. — DOI:10.1007/BF02788872.
  • T. Chan. [3] — 1999. з джерела 4 листопада 2010
  • B. Chazelle, L. J. Guibas, D. T. Lee. The power of geometric duality // BIT. — 1985. — Т. 25, вип. 1. — С. 76–90. — DOI:10.1007/BF01934990.
  • K. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. — . — 1990. — Т. 5. — С. 99–160. — DOI:10.1007/BF02187783.
  • Richard Cole, Jeffrey S. Salowe, W. L. Steiger, Endre Szemerédi. An optimal-time algorithm for slope selection // . — 1989. — Т. 18, вип. 4. — С. 792–810. — DOI:10.1137/0218055.
  • R. Cole, M. Sharir, C.-K. Yap. On k-hulls and related problems // SIAM Journal on Computing. — 1987. — Т. 16, вип. 1. — С. 61–77. — DOI:10.1137/0216005.
  • D. W. Crowe, T. A. McKee. Sylvester's problem on collinear points // . — Mathematical Association of America, 1968. — Т. 41, вип. 1. — С. 30–34. — DOI:10.2307/2687957.
  • T. L. Dey. Improved bounds for planar k-sets and related problems // . — 1998. — Т. 19, вип. 3. — С. 373–382. — DOI:10.1007/PL00009354.
  • G. Dirac. Collinearity properties of sets of points. — Quart. J. Math. — 1951. — Т. 2. — С. 221–227. — DOI:10.1093/qmath/2.1.221.
  • H. Edelsbrunner. Algorithms in Combinatorial Geometry. — Springer-Verlag, 1987. — (EATCS Monographs in Theoretical Computer Science) — .
  • H. Edelsbrunner, L. J. Guibas. Topologically sweeping an arrangement // Journal of Computer and System Sciences. — 1989. — Т. 38, вип. 1. — С. 165–194. — DOI:10.1016/0022-0000(89)90038-X.
  • H. Edelsbrunner, L. J. Guibas, M. Sharir. The complexity and construction of many faces in arrangements of lines and of segments // . — 1990. — Т. 5, вип. 1. — С. 161–196. — DOI:10.1007/BF02187784.
  • H. Edelsbrunner, J. O'Rourke, R. Seidel. Constructing arrangements of lines and hyperplanes with applications // SIAM Journal on Computing. — 1986. — Т. 15, вип. 2. — С. 341–363. — DOI:10.1137/0215024.
  • H. Edelsbrunner, E. Welzl. Constructing belts in two-dimensional arrangements with applications // SIAM Journal on Computing. — 1986. — Т. 15, вип. 1. — С. 271–284. — DOI:10.1137/0215019.
  • D. Eppstein. Cubic partial cubes from simplicial arrangements // Electronic J. Combinatorics. — 2006. — Т. 13, вип. 1, R79. — С. 1–14. — arXiv:math.CO/0510263. з джерела 14 лютого 2012. Процитовано 26 червня 2021.
  • D. Eppstein, J.-Cl. Falmagne, S. Ovchinnikov. Media Theory. — Springer-Verlag, 2007.
  • D. Eppstein, D. Hart. Proc. 10th ACM/SIAM Symp. Discrete Algorithms (SODA '99). — 1999. — С. 310–316.
  • P. Erdős, L. Lovász, A. Simmons, E. G. Straus. A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). — Amsterdam : North-Holland, 1973. — С. 139–149.
  • J. Erickson. Shortest paths in line arrangements. — 1997. з джерела 3 грудня 2008. Процитовано 26 червня 2021.
  • S. Fortune, V. Milenkovic. Proc. 7th ACM Symp. Computational Geometry (SoCG '91). — 1991. — С. 334–341. — DOI:10.1145/109648.109685.
  • H. de Fraysseix, P. Ossona de Mendez. Proc. 11th Int. Symp. Graph Drawing (GD 2003). — Springer-Verlag, 2003. — С. 71–85. — (Lecture Notes in Computer Science)
  • Z. Füredi, I. Palásti. [4] — Proceedings of the American Mathematical Society. — 1984. — Т. 92. — С. 561–566. — DOI:10.2307/2045427. з джерела 3 березня 2016
  • D. Greene, F. F. Yao. Proc. 27th IEEE Symp. Foundations of Computer Science. — 1986. — С. 143–152. — DOI:10.1109/SFCS.1986.19.
  • B. Grünbaum. Arrangements and Spreads. — Providence, R.I. : American Mathematical Society, 1972. — Т. 10. — (Regional Conference Series in Mathematics)
  • B. Grünbaum. A catalogue of simplicial arrangements in the real projective plane. — 2005. з джерела 22 липня 2012. Процитовано 26 червня 2021.
  • L. M. Kelly, W. O. J. Moser. On the number of ordinary lines determined by n points // Canad. J. Math.. — 1958. — Т. 10. — С. 210–219. — DOI:10.4153/CJM-1958-024-6.
  • F. T. Leighton. Complexity Issues in VLSI. — Cambridge, MA : MIT Press, 1983. — (Foundations of Computing Series)
  • F. Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade // Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig. — 1926. — Т. 78. — С. 256–267.
  • L. Lovász. On the number of halving lines // Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica. — 1971. — Т. 14. — С. 107–108.
  • J. Matoušek. Lower bounds on the length of monotone paths in arrangements // . — 1991. — Т. 6, вип. 1. — С. 129–134. — DOI:10.1007/BF02574679.
  • E. Melchior. Über Vielseite der projektiven Ebene // Deutsche Mathematik. — 1940. — Т. 5. — С. 461–475.
  • V. Milenkovic. Proc. 30th IEEE Symp. Foundations of Computer Science (FOCS '89). — 1989. — С. 500–505. — DOI:10.1109/SFCS.1989.63525.
  • Th. Motzkin. The Lines and Planes Connecting the Points of a Finite Set. — Transactions of the American Mathematical Society. — American Mathematical Society, 1951. — Т. 70. — С. 451–464. — DOI:10.2307/1990609.
  • G. B. Purdy. Triangles in arrangements of lines // Discrete Math.. — 1979. — Т. 25, вип. 2. — С. 157–163. — DOI:10.1016/0012-365X(79)90018-9.
  • G. B. Purdy. Triangles in arrangements of lines, II // Proceedings of the American Mathematical Society. — 1980. — Т. 79. — С. 77–81. — DOI:10.1090/S0002-9939-1980-0560588-4.
  • J.-P. Roudneff. Arrangements of lines with a minimum number of triangles are simple // . — 1988. — Т. 3, вип. 1. — С. 97–102. — DOI:10.1007/BF02187900.
  • Marcus Schaefer. Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. — Springer-Verlag, 2010. — Т. 5849. — С. 334–344. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11805-0_32.
  • P. W. Shor. Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift / P. Gritzmann, B. Sturmfels. — Providence, R.I. : American Mathematical Society, 1991. — Т. 4. — С. 531–554. — (DIMACS Series in Discrete Mathematics and Theoretical Computer Science)
  • J. Steiner. Einige Gesetze über die Theilung der Ebene und des Raumes // . — 1826. — Т. 1. — С. 349–364.
  • T. O. Strommer. Triangles in arrangements of lines // Journal of Combinatorial Theory, Series A. — 1977. — Т. 23, вип. 3. — С. 314–320. — DOI:10.1016/0097-3165(77)90022-X.
  • L. A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // . — 1997. — Т. 6, вип. 3. — С. 353–358. — DOI:10.1017/S0963548397002976.
  • G. Tóth. Point sets with many k-sets // . — 2001. — Т. 26, вип. 2. — С. 187–194. — DOI:10.1007/s004540010022.

Посилання

    Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

    Konfiguraciya pryamih abo rozbittya ploshini pryamimi ce rozbittya ploshini utvorene naborom pryamih Konfiguraciyi pryamih vivchaye kombinatorna geometriya a v obchislyuvalnij geometriyi buduyutsya algoritmi dlya efektivnoyi pobudovi konfiguracij Simplicijna konfiguraciya pryamih livoruch i prosta konfiguraciya pryamih pravoruch ViznachennyaDlya bud yakoyi mnozhini A pryamih na evklidovij ploshini mozhna viznachiti vidnoshennya ekvivalentnosti na tochkah ploshini za yakim dvi tochki p i q ekvivalentni yaksho dlya bud yakoyi pryamoyi l iz A abo p i q obidvi lezhat na pryamij l abo voni lezhat u tij samij vidkritij pivploshini obmezhenij pryamoyu l Yaksho A skinchenna abo lokalno skinchenna klasi ekvivalentnosti cih vidnoshen nalezhat trom grupam vnutrishnosti obmezhenih abo neobmezhenih opuklih mnogokutnikiv komirki rozbittya zv yazni komponenti pidmnozhini tochok ploshini sho ne mistyatsya na zhodnij iz pryamih iz A vidkriti vidrizki i vidkriti neskinchenni promeni rebra rozbittya zv yazni komponenti tochok okremoyi pryamoyi sho ne nalezhat niyakij inshij pryamij iz A okremi tochki vershini rozbittya peretin dvoh abo bilshe pryamih iz A Ci tri tipi ob yektiv z yednani razom utvoryuyut klitinne rozbittya sho pokrivaye ploshinu Kazhut sho dvi konfiguraciyi pryamih izomorfni abo kombinatorno ekvivalentni yaksho isnuye vidpovidnist mizh ob yektami v klitinnih rozbittyah yake odin do odnogo zberigaye sumizhnist Skladnist naborivVivchennya konfiguracij pryamih pochav Yakob Shtejner yakij doviv pershu mezhu najbilshogo chisla elementiv riznih tipiv yake mozhe mistiti konfiguraciya Konfiguraciya z n pryamih maye ne bilshe n n 1 2 vershin po odnij na paru peretinnih pryamih Cej maksimum dosyagayetsya na prostih konfiguraciyah Konfiguraciya nazivayetsya prostoyu yaksho 1 niyaki tri pryami ne peretinayutsya v odnij tochci 2 niyaki dvi pryami ne paralelni U bud yakij konfiguraciyi bude n neskinchennih spryamovanih vniz promeniv po odnomu na pryamu Ci promeni vidokremlyuyut n 1 komirok rozbittya neobmezhenih znizu Reshta komirok mayut yedinu najnizhchu vershinu i kozhna taka vershina ye nizhnoyu dlya yedinoyi komirki tak sho chislo komirok rozbittya dorivnyuye chislu vershin plyus n 1 abo ne perevishuye n n 1 2 1 div Centralni bagatokutni chisla Chislo reber rozbittya ne perevishuye n2 sho mozhna pobachiti abo za dopomogoyu ejlerovoyi harakteristiki pidstavivshi chislo vershin i komirok abo skoristavshis sposterezhennyam sho kozhnu pryamu rozdileno maksimum na n reber inshimi n 1 pryamimi Znovu girshim vipadkom na yakomu mezha dosyagayetsya ye prosti konfiguraciyi pryamih Zona pryamoyi l u nabori pryamih ce nabir komirok yaki mayut rebra sho lezhat na l Teorema pro zonu stverdzhuye sho povne chislo reber v oseredkah okremoyi zoni linijne Tochnishe povne chislo reber komirok iz zoni pryamoyi sho mistyatsya po odin bik vid pryamoyi l ne bilsh yak 5n 1 a povne chislo reber komirok sho lezhat po obidva boki vid l ne perevishuye 9 5 n 1 displaystyle lfloor 9 5n rfloor 1 Zagalnishe povna skladnist komirok rozbittya yaki peretinayutsya opukloyu krivoyu dorivnyuye O n a n de a poznachaye obernenu funkciyu Akkermana sho mozhna pokazati vihodyachi z en Pidsumovuyuchi skladnist usih zon mozhna viyaviti sho suma kvadrativ skladnostej komirok u rozbitti dorivnyuye O n2 en konfiguraciyi pryamih ce lamana utvorena rebrami yaki mayut rivno k inshih pryamih pid neyu tobto promin opushenij vniz vid rebra peretinaye rivno k pryamih a k riven ce vsi chastini konfiguraciyi pryamih sho mistyatsya pid k rivnem Znahodzhennya verhnoyi i nizhnoyi mezh skladnosti dlya k rivniv zalishayetsya golovnoyu vidkritoyu problemoyu diskretnoyi geometriyi Krashoyu verhnoyu mezheyu ye O nk1 3 todi yak krashoyu nizhnoyu W n exp c logk 1 2 Vidomo sho maksimalna skladnist k rivnya dorivnyuye 8 nk k riven ye okremim vipadkom monotonnogo shlyahu v rozbitti ploshini tobto poslidovnosti reber yaki peretinayut bud yaku vertikalnu pryamu v okremij tochci Odnak monotonni shlyahi mozhut buti skladnishimi nizh k rivni isnuyut nabori pryamih i monotonni shlyahi v cih naborah de chislo tochok na yakih shlyah zminyuye napryamok dorivnyuye W n2 o 1 Hocha okrema komirka v rozbitti mozhe buti obmezhena vsima n pryamimi nemozhlivo v zagalnomu vipadku shob m riznih komirok buli obmezheni n pryamimi Navpaki povna skladnist m komirok majzhe dorivnyuye 8 m2 3n2 3 n i majzhe taka zh mezha z yavlyayetsya v teoremi Semeredi Trottera pro incidenciyu tochok i pryamih na ploshini Proste dovedennya cogo faktu viplivaye z nerivnosti chisla peretiniv yaksho m komirok mayut zagalom x n reber mozhna stvoriti graf z m vershinami po odnij na komirku i x rebrami po odnomu na paru poslidovnih komirok na tij samij pryamij Rebra cogo grafa mozhna namalyuvati yak krivi yaki ne peretinayutsya vseredini komirok vidpovidnih kincevim vershinam reber a potim sliduyut po pryamih naboru Otzhe na comu malyunku ye O n2 peretiniv Odnak za nerivnistyu chisla peretiniv isnuye W x3 m2 peretiniv Shob vikonuvalisya obidvi nerivnosti x maye buti O m2 3n2 3 Proyektivni konfiguraciyi i proyektivna dvoyististChasto zruchno vivchati konfiguraciyu pryamih ne v evklidovomu prostori a na proyektivnij ploshini oskilki v proyektivnij geometriyi bud yaka para pryamih maye tochku peretinu Na proyektivnij ploshini mi ne mozhemo viznachiti rozbittya z vikoristannyam bokiv pryamih pryama na proyektivnij ploshini ne dilit ploshinu na dva rizni boki ale mi vse zh mozhemo viznachiti komirki rozbittya yak zv yazni komponenti tochok yaki ne lezhat na zhodnij pryamij Rebrami budut zv yazni komponenti sho skladayutsya z mnozhini tochok yaki nalezhat okremij pryamij a vershinami budut tochki de dvi abo bilshe pryamih peretinayutsya Nabir pryamih na proyektivnij ploshini vidriznyayetsya vid jogo evklidovogo dvijnika oskilki dva evklidovih promeni po obidva boki vid pryamoyi zaminyuyutsya odnim rebrom na proyektivnij ploshini a pari neobmezhenih evklidovih komirok zaminyuyutsya na proyektivnij ploshini v yedini komirki Z oglyadu na proyektivnu dvoyistist bagato tverdzhen pro kombinatorni vlastivosti tochok na ploshini mozhna legko zrozumiti v ekvivalentnij dvoyistij formi pro konfiguraciyi pryamih Napriklad teorema Silvestra yaka stverdzhuye sho bud yaka nekolinearna mnozhina tochok na ploshini maye prostu pryamu yaka mistit rivno dvi tochki peretvoryuyetsya za proyektivnoyu dvoyististyu na tverdzhennya sho bud yaka konfiguraciya pryamih yaka maye bilshe nizh odnu vershinu maye prostu tochku vershinu v yakij peretinayutsya vsogo dvi pryami Najranishe vidome dovedennya teoremi Silvestra Melhiorom Melchior 1940 vikoristovuye ejlerovu harakteristiku Trikutniki v naborah pryamihKonfiguraciyu pryamih u proyektivnij ploshini nazivayut simplicijnoyu yaksho bud yaka komirka rozbittya obmezhena rivno troma rebrami Simplicijni konfiguraciyi pershim vivchav Melhior Tri neskinchennih simejstva simplicijnih naboriv pryamih vidomi Majzhe puchok skladayetsya z n 1 pryamih sho prohodyat cherez odnu tochku i odniyeyi pryamoyi yaka cherez cyu tochku ne prohodit Simejstvo pryamih utvorenih storonami pravilnogo mnogokutnika razom z osyami simetriyi Storoni i osi simetriyi parnogo pravilnogo mnogokutnika razom iz pryamoyu na neskinchennosti Krim togo ye bagato inshih prikladiv odinichnih simplicijnih konfiguracij yaki ne vmishayutsya v yakes vidome neskinchenne simejstvo Yak pishe Gryunbaum simplicijni nabori pryamih z yavlyayutsya yak prikladi abo kontrprikladi v bagatoh kontekstah kombinatornoyi geometriyi i yiyi zastosuvan Napriklad Artye Gryunbaum i Llibre vikoristovuvali simplicijni nabori pryamih dlya pobudovi kontrprikladiv do gipotezi pro zv yazok mizh stepenyami naboru diferencialnih rivnyan i chislom invariantnih pryamih yaki rivnyannya mozhut mati Obidva vidomih kontrprikladi do gipotezi Diraka Mockina yaka stverdzhuye sho bud yaka konfiguraciya n pryamih maye shonajmenshe n 2 prostih tochok simplicijni Dvoyistim grafom konfiguraciyi pryamih u yakij isnuye odna vershina dlya komirki i odne rebro sho z yednuye vershini vidpovidni komirkam iz spilnim rebrom u konfiguraciyi ye chastkovij kub graf u yakomu vershini mozhna poznachiti bitovimi vektorami tak sho vidstan na grafi dorivnyuye vidstani Gemminga mizh poznachkami U razi konfiguracij pryamih kozhna koordinata nabuvaye znachennya 0 dlya reber po odin bik vid pryamoyi i 1 dlya reber po inshij bik Dvoyisti grafi simplicijnih konfiguracij vikoristovuvalisya dlya pobudovi neskinchennih simejstv 3 regulyarnih chastkovih kubiv izomorfnih grafam prostogo zonoedra Cikavo takozh vivchiti ekstremalni kilkosti trikutnih komirok u konfiguraciyi yaka ne obov yazkovo simplicijna U bud yakij konfiguraciyi maye buti shonajmenshe n trikutnikiv Bud yaka konfiguraciya sho maye tilki n trikutnikiv maye buti prostoyu Vidomo sho najbilshe mozhlive chislo trikutnikiv u prostij konfiguraciyi obmezhene zverhu chislom n n 1 3 a nizhnya mezha dorivnyuye n n 3 3 Nizhnya mezha dosyagayetsya na deyakih pidmnozhinah diagonalej pravilnogo 2n kutnika Dlya neprostih konfiguracij najbilshe chislo trikutnikiv shozhe ale silnishe obmezhene U tisno pov yazanij zadachi Kobona pro trikutniki zapituyetsya pro najbilshu kilkist neperekrivnih skinchennih trikutnikiv ne obov yazkovo granej u konfiguraciyi na evklidovij ploshini Dlya deyakih ale ne dlya vsih znachen n mozhlivo n n 2 3 trikutnikiv Multisitkovi mozayiki i mozayiki Penrouza en Dvoyistij graf prostoyi konfiguraciyi pryamih mozhna podati geometrichno yak nabir rombiv po odnomu na vershinu konfiguraciyi zi storonami perpendikulyarnimi do pryamih yaki peretinayutsya u vershini Ci rombi mozhna ob yednati z utvorennyam zamoshennya opuklogo mnogokutnika v razi konfiguraciyi skinchennogo chisla pryamih abo vsiyeyi ploshini v razi lokalno skinchennih konfiguracij z neskinchennim chislom pryamih De Brejn doslidzhuvav okremi vipadki ciyeyi pobudovi v yakih konfiguraciya pryamih skladayetsya z k mnozhin paralelnih pryamih z rivnim viddalennyam odna vid odnoyi Dlya dvoh perpendikulyarnih simejstv paralelnih pryamih cya pobudova daye kvadratnij parket na ploshini a dlya troh simejstv pryamih pid kutom 120 odne vidnosno odnogo sho formuyut pobudova daye Odnak dlya bilshogo chisla simejstv pryamih cya pobudova daye aperiodichni mozayiki Zokrema dlya p yati simejstv pryamih z rivnimi kutami odne vidnosno odnogo abo yak de Brejn nazivaye cyu konfiguraciyu pentagrida ce daye simejstvo zamoshen yake vklyuchaye rombichnu versiyu mozayik Penrouza ce neskinchenna konfiguraciya pryamih sho utvoryuye periodichne zamoshennya yake nagaduye multisitku z chotirma paralelnimi rodinami ale v yakij dva simejstva mayut bilshu vidstan mizh pryamimi nizh v inshih dvoh i v yakih nabir pryamih ye simplicijnim a ne prostim Dvoyistoyu mozayikoyu ye ru Podibnim chinom trikutnij parket ye neskinchennoyu simplicijnoyu konfiguraciyeyu pryamih z troma simejstvami paralelnih pryamih u yakij dvoyistoyu mozayikoyu ye shestikutnij parket a en ye neskinchennoyu simplicijnoyu konfiguraciyeyu pryamih iz shistma simejstvami paralelnih pryamih i dvoma vidstanyami mizh pryamimi v simejstvah yaka dvoyista en AlgoritmiKonstruyuvannya konfiguraciyi oznachaye obchislennya podannya vershin reber i komirok konfiguraciyi pryamih razom z yih vzayemozv yazkami pri zadanni spisku pryamih u nabori napriklad yak u dvozv yaznomu spisku reber Zgidno z teoremoyu pro zoni nabori mozhna pobuduvati efektivno za dopomogoyu inkrementnogo algoritmu yakij dodaye po odnij pryamij za krok do naboru pryamih dodanih na poperednih krokah kozhnu novu pryamu mozhna dodati za chas proporcijnij yiyi zoni sho v rezultati daye chas O n2 Odnak vimogi do pam yati v comu algoritmi visoki tak sho mozhe buti zruchnishim pererahuvannya vsih vlastivostej konfiguraciyi v algoritmi yakij ne zberigaye vsyu konfiguraciyu v pam yati Ce mozhna zrobiti efektivno za chas O n2 i z pam yattyu O n za dopomogoyu algoritmichnoyi tehniki vidomoyi yak topologichne vimitannya Tochne obchislennya konfiguraciyi pryamih vimagaye obchislyuvalnoyi tochnosti v kilka raziv bilshoyi nizh vhidni dani koordinati yaksho pryama zadayetsya dvoma tochkami na nij koordinati konfiguraciyi vershin mozhut zazhadati v 4 razi bilshoyi tochnosti nizh tochnist tochok vhidnih danih Tomu v obchislyuvalnij geometriyi vivchayut takozh algoritmi pobudovi konfiguracij efektivno z obmezhenoyu chiselnoyu tochnistyu Takozh doslidniki vivchali efektivni algoritmi pobudovi menshih chastin konfiguraciyi takih yak zoni k rivni abo mnozhini komirok sho mistyat zadanij nabir tochok Zadacha znahodzhennya konfiguraciyi vershin z medianoyu x koordinat vinikaye v dvoyistij formi v robastnih statistikah yak zadacha obchislennya mnozhini tochok Mark van Kreveld zaproponuvav algoritmichnu zadachu obchislennya najkorotshogo shlyahu mizh vershinami v konfiguraciyi pryamih de shlyahi obmezheni rebrami konfiguraciyi Zadacha stavitsya tak chi ye algoritmi sho pracyuyut za chas menshij nizh kvadratichnij yakij znadobivsya b dlya algoritmu poshuku najkorotshogo shlyahu v povnomu grafi konfiguraciyi Vidomij aproksimacijnij algoritm i zadachu mozhna efektivno rozv yazati dlya pryamih yaki rozbivayutsya na nevelike chislo simejstv paralelnih pryamih sho tipovo dlya vulic mist odnak zadacha v zagalnomu viglyadi zalishayetsya vidkritoyu Variaciyi ta uzagalnennyaKonfiguraciya psevdopryamih Konfiguraciya psevdopryamih ce konfiguraciya krivih sho mayut shozhi topologichni vlastivosti zi konfiguraciyeyu pryamih Yih najprostishe mozhna viznachiti na proyektivnij ploshini yak prosti zamknuti krivi z yakih bud yaki dvi peretinayutsya transversalno v yedinij tochci Kazhut sho konfiguraciya psevdopryamih roztyazhna yaksho vona kombinatorno ekvivalentna konfiguraciyi pryamih Zadacha vidriznennya roztyazhnih naboriv vid neroztyazhnih ye NP povnoyu Bud yaku konfiguraciyu skinchennogo chisla psevdopryamih mozhna rozshiriti tak sho psevdopryami stayut pryamimi v neevklidovij geometriyi incidentnosti v yakij bud yaki dvi tochki topologichnoyi ploshini z yednani yedinoyu pryamoyu yak na evklidovij ploshini ale v yakij inshi aksiomi evklidovoyi geometriyi mozhut ne vikonuvatisya Neroztyazhnij nabir dev yati psevdopryamih Usi nabori z chislom psevdopryamih menshe dev yati roztyazhni Za teoremoyu Pappa cyu konfiguraciyu ne mozhna realizuvati v proyektivnij ploshini nad bud yakim polem Giperbolichna konfiguraciya pryamih kombinatorno ekvivalentna diagrami hord vikoristanij Ageyevim dlya dovedennya sho kolovij graf bez trikutnikiv mozhe inodi vimagati 5 koloriv Ploshina Lobachevskogo Inshim tipom neevklidovoyi geometriyi ye ploshina Lobachevskogo i konfiguraciyi giperbolichnih pryamih u cij geometriyi takozh vivchalisya Bud yaka skinchenna mnozhina pryamih na evklidovij ploshini maye kombinatorno ekvivalentnu konfiguraciyu v giperbolichnij ploshini napriklad ukladayuchi vershini naboru u velike kolo i interpretuyuchi jogo vnutrishnist yak model Klyajna giperbolichnoyi ploshini Odnak u giperbolichnomu nabori pryamih mozhna uniknuti peretinannya pryamih bez vimogi paralelnosti pryamih Graf peretiniv pryamih u giperbolichnij konfiguraciyi ye kolovim grafom Vidpovidne ponyattya giperbolichnoyi konfiguraciyi pryamih dlya psevdopryamih slabka konfiguraciya psevdopryamih simejstvo krivih yake maye ti zh topologichni vlastivosti sho j pryami taki sho bud yaki dvi krivi v simejstvi abo peretinayutsya v odnij tochci abo ne peretinayutsya vzagali Div takozhKonfiguraciya nabir pryamih i mnozhina tochok de vsi pryami mistyat odne i te same chislo tochok a vsi tochki nalezhat odnakovomu chislu pryamih Konfiguraciya rozbittya prostoru rozbittya ploshini zadane krivimi abo prostoriv vishih rozmirnostej zadane poverhnyami koli ne potribno shob poverhnya bula ploshinoyu PrimitkiV anglomovnij literaturi arrangement sho chasto perekladayut yak konfiguraciya odnak isnuye inshij termin configuration yakij prirodno perekladati takozh slovom konfiguraciya Inkoli vikoristovuyut termin nabir pryamih inkoli rozbittya pryamimi abo giperploshinami U lokalno skinchennih naborah bud yaka obmezhena pidmnozhina ploshini mozhe peretinatisya lishe skinchennim chislom pryamih Grunbaum 1972 s 4 Steiner 1826 Agarwal Sharir 2000 Dlya komirok u yakih ye gorizontalne nizhnye rebro vibirayemo vershinu pravoruch Chazelle et al 1985 Edelsbrunner 1987 Edelsbrunner O Rourke Seidel 1986 Bern Eppstein Plassman Yao 1991 Aronov Matousek Sharir 1994 Dey 1998 Toth 2001 Zadachu obmezhennya skladnosti k rivniv upershe vivchali Lovash Lovasz 1971 i grupa Erdesh Simons Straus Erdos et al 1973 Alon Gyori 1986 Balogh ta in 2004 see also Matousek 1991 Canham 1969 Clarkson et al 1990 Ajtai Chvatal Newborn Szemeredi 1982 Leighton 1983 Szekely 1997 Melchior 1940 Grunbaum 2005 Grunbaum 1972 Artes Grunbaum Llibre 1998 Crowe McKee 1968 Dirac 1951 Kelly Moser 1958 Grunbaum 1972 s 18 Eppstein Falmagne Ovchinnikov 2007 Eppstein 2006 Levi 1926 Roudneff 1988 Furedi Palasti 1984 Purdy 1979 Purdy 1980 Strommer 1977 de Bruijn 1981 Edelsbrunner Guibas 1989 Fortune Milenkovic 1991 Greene Yao 1986 Milenkovic 1989 Aharoni et al 1999 Agarwal de Berg Matousek Schwarzkopf 1998 Chan 1999 Cole Sharir Yap 1987 Edelsbrunner Welzl 1986 Agarwal 1990 Agarwal Matousek Sharir 1998 Edelsbrunner Guibas Sharir 1990 Cole Salowe Steiger Szemeredi 1989 Erickson 1997 Bose et al 1996 Eppstein Hart 1999 Agarwal Sharir 2002 Shor 1991 Schaefer 2010 Ageev 1996 de Fraysseix Ossona de Mendez 2003 Alternativne viznachennya Shora Shor 1991 psevdopryama ye obrazom pryamoyi gomeomorfizmu ploshini LiteraturaP K Agarwal Partitioning arrangements of lines II Applications 1990 T 5 vip 1 S 533 573 DOI 10 1007 BF02187809 P K Agarwal M de Berg J Matousek O Schwarzkopf Constructing levels in arrangements and higher order Voronoi diagrams SIAM Journal on Computing 1998 T 27 vip 3 S 654 667 DOI 10 1137 S0097539795281840 P K Agarwal J Matousek M Sharir Computing many faces in arrangements of lines and segments SIAM Journal on Computing 1998 T 27 vip 2 S 491 505 DOI 10 1137 S009753979426616X P K Agarwal M Sharir 1 Elsevier 2000 S 49 119 z dzherela 10 chervnya 2007 P K Agarwal M Sharir Proc 13th ACM SIAM Symp Discrete algorithms SODA 02 San Francisco Society for Industrial and Applied Mathematics 2002 S 800 809 A A Ageev A triangle free circle graph with chromatic number 5 Discrete Math 1996 T 152 S 295 298 DOI 10 1016 0012 365X 95 00349 2 Y Aharoni D Halperin I Hanniel S Har Peled C Linhart Proc 3rd Int Worksh Algorithm Engineering WAE 99 Springer Verlag 1999 T 1668 S 139 153 Lecture Notes in Computer Science DOI 10 1007 3 540 48318 7 13 M Ajtai V Chvatal M Newborn E Szemeredi Theory and Practice of Combinatorics North Holland 1982 T 60 S 9 12 North Holland Mathematics Studies N Alon E Gyori The number of small semi spaces of a finite set of points in the plane Journal of Combinatorial Theory Series A 1986 T 41 S 154 157 DOI 10 1016 0097 3165 86 90122 6 B Aronov J Matousek M Sharir On the sum of squares of cell complexities in hyperplane arrangements Journal of Combinatorial Theory Series A 1994 T 65 vip 2 S 311 321 DOI 10 1016 0097 3165 94 90027 2 J C Artes B Grunbaum J Llibre On the number of invariant straight lines for polynomial differential systems Pacific Journal of Mathematics 1998 T 184 vip 2 S 207 230 DOI 10 2140 pjm 1998 184 207 z dzherela 18 lipnya 2010 Procitovano 26 chervnya 2021 J Balogh O Regev C Smyth W Steiger M Szegedy Long monotone paths in line arrangements 2004 T 32 vip 2 S 167 176 DOI 10 1007 s00454 004 1119 1 M W Bern D Eppstein P E Plassman F F Yao Discrete and Computational Geometry Papers from the DIMACS Special Year J E Goodman R Pollack W Steiger Amer Math Soc 1991 S 45 66 DIMACS Ser Discrete Math and Theoretical Computer Science P Bose W Evans D G Kirkpatrick M McAllister J Snoeyink Proc 8th Canadian Conf Computational Geometry 1996 S 143 148 N G de Bruijn 2 1981 T 43 S 38 66 z dzherela 7 travnya 2021 R Canham A theorem on arrangements of lines in the plane Israel J Math 1969 T 7 vip 4 S 393 397 DOI 10 1007 BF02788872 T Chan 3 1999 z dzherela 4 listopada 2010 B Chazelle L J Guibas D T Lee The power of geometric duality BIT 1985 T 25 vip 1 S 76 90 DOI 10 1007 BF01934990 K Clarkson H Edelsbrunner L J Guibas M Sharir E Welzl Combinatorial complexity bounds for arrangements of curves and spheres 1990 T 5 S 99 160 DOI 10 1007 BF02187783 Richard Cole Jeffrey S Salowe W L Steiger Endre Szemeredi An optimal time algorithm for slope selection 1989 T 18 vip 4 S 792 810 DOI 10 1137 0218055 R Cole M Sharir C K Yap On k hulls and related problems SIAM Journal on Computing 1987 T 16 vip 1 S 61 77 DOI 10 1137 0216005 D W Crowe T A McKee Sylvester s problem on collinear points Mathematical Association of America 1968 T 41 vip 1 S 30 34 DOI 10 2307 2687957 T L Dey Improved bounds for planar k sets and related problems 1998 T 19 vip 3 S 373 382 DOI 10 1007 PL00009354 G Dirac Collinearity properties of sets of points Quart J Math 1951 T 2 S 221 227 DOI 10 1093 qmath 2 1 221 H Edelsbrunner Algorithms in Combinatorial Geometry Springer Verlag 1987 EATCS Monographs in Theoretical Computer Science ISBN 978 3 540 13722 1 H Edelsbrunner L J Guibas Topologically sweeping an arrangement Journal of Computer and System Sciences 1989 T 38 vip 1 S 165 194 DOI 10 1016 0022 0000 89 90038 X H Edelsbrunner L J Guibas M Sharir The complexity and construction of many faces in arrangements of lines and of segments 1990 T 5 vip 1 S 161 196 DOI 10 1007 BF02187784 H Edelsbrunner J O Rourke R Seidel Constructing arrangements of lines and hyperplanes with applications SIAM Journal on Computing 1986 T 15 vip 2 S 341 363 DOI 10 1137 0215024 H Edelsbrunner E Welzl Constructing belts in two dimensional arrangements with applications SIAM Journal on Computing 1986 T 15 vip 1 S 271 284 DOI 10 1137 0215019 D Eppstein Cubic partial cubes from simplicial arrangements Electronic J Combinatorics 2006 T 13 vip 1 R79 S 1 14 arXiv math CO 0510263 z dzherela 14 lyutogo 2012 Procitovano 26 chervnya 2021 D Eppstein J Cl Falmagne S Ovchinnikov Media Theory Springer Verlag 2007 D Eppstein D Hart Proc 10th ACM SIAM Symp Discrete Algorithms SODA 99 1999 S 310 316 P Erdos L Lovasz A Simmons E G Straus A Survey of Combinatorial Theory Proc Internat Sympos Colorado State Univ Fort Collins Colo 1971 Amsterdam North Holland 1973 S 139 149 J Erickson Shortest paths in line arrangements 1997 z dzherela 3 grudnya 2008 Procitovano 26 chervnya 2021 S Fortune V Milenkovic Proc 7th ACM Symp Computational Geometry SoCG 91 1991 S 334 341 DOI 10 1145 109648 109685 H de Fraysseix P Ossona de Mendez Proc 11th Int Symp Graph Drawing GD 2003 Springer Verlag 2003 S 71 85 Lecture Notes in Computer Science Z Furedi I Palasti 4 Proceedings of the American Mathematical Society 1984 T 92 S 561 566 DOI 10 2307 2045427 z dzherela 3 bereznya 2016 D Greene F F Yao Proc 27th IEEE Symp Foundations of Computer Science 1986 S 143 152 DOI 10 1109 SFCS 1986 19 B Grunbaum Arrangements and Spreads Providence R I American Mathematical Society 1972 T 10 Regional Conference Series in Mathematics B Grunbaum A catalogue of simplicial arrangements in the real projective plane 2005 z dzherela 22 lipnya 2012 Procitovano 26 chervnya 2021 L M Kelly W O J Moser On the number of ordinary lines determined by n points Canad J Math 1958 T 10 S 210 219 DOI 10 4153 CJM 1958 024 6 F T Leighton Complexity Issues in VLSI Cambridge MA MIT Press 1983 Foundations of Computing Series F Levi Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade Ber Math Phys Kl Sachs Akad Wiss Leipzig 1926 T 78 S 256 267 L Lovasz On the number of halving lines Annales Universitatis Scientiarum Budapestinensis de Rolando Eotvos Nominatae Sectio Mathematica 1971 T 14 S 107 108 J Matousek Lower bounds on the length of monotone paths in arrangements 1991 T 6 vip 1 S 129 134 DOI 10 1007 BF02574679 E Melchior Uber Vielseite der projektiven Ebene Deutsche Mathematik 1940 T 5 S 461 475 V Milenkovic Proc 30th IEEE Symp Foundations of Computer Science FOCS 89 1989 S 500 505 DOI 10 1109 SFCS 1989 63525 Th Motzkin The Lines and Planes Connecting the Points of a Finite Set Transactions of the American Mathematical Society American Mathematical Society 1951 T 70 S 451 464 DOI 10 2307 1990609 G B Purdy Triangles in arrangements of lines Discrete Math 1979 T 25 vip 2 S 157 163 DOI 10 1016 0012 365X 79 90018 9 G B Purdy Triangles in arrangements of lines II Proceedings of the American Mathematical Society 1980 T 79 S 77 81 DOI 10 1090 S0002 9939 1980 0560588 4 J P Roudneff Arrangements of lines with a minimum number of triangles are simple 1988 T 3 vip 1 S 97 102 DOI 10 1007 BF02187900 Marcus Schaefer Graph Drawing 17th International Symposium GS 2009 Chicago IL USA September 2009 Revised Papers Springer Verlag 2010 T 5849 S 334 344 Lecture Notes in Computer Science DOI 10 1007 978 3 642 11805 0 32 P W Shor Applied Geometry and Discrete Mathematics The Victor Klee Festschrift P Gritzmann B Sturmfels Providence R I American Mathematical Society 1991 T 4 S 531 554 DIMACS Series in Discrete Mathematics and Theoretical Computer Science J Steiner Einige Gesetze uber die Theilung der Ebene und des Raumes 1826 T 1 S 349 364 T O Strommer Triangles in arrangements of lines Journal of Combinatorial Theory Series A 1977 T 23 vip 3 S 314 320 DOI 10 1016 0097 3165 77 90022 X L A Szekely Crossing numbers and hard Erdos problems in discrete geometry 1997 T 6 vip 3 S 353 358 DOI 10 1017 S0963548397002976 G Toth Point sets with many k sets 2001 T 26 vip 2 S 187 194 DOI 10 1007 s004540010022 Posilannya

    Дата публікації:
    Топ