Вікіпедія

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

розбиття площини, утворене набором прямих

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

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

Визначення ред.

Для будь-якої множини 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, див. Центральні багатокутні числа. Число ребер розбиття не перевищує 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]. Три нескінченних сімейства симпліційних наборів прямих відомі:

  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 трикутників.

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

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

Двоїстий граф простої конфігурації прямих можна подати геометрично як набір ромбів, по одному на вершину конфігурації зі сторонами, перпендикулярними до прямих, які перетинаються у вершині. Ці ромби можна об'єднати з утворенням замощення опуклого многокутника в разі конфігурації скінченного числа прямих або всієї площини в разі локально скінченних конфігурацій з нескінченним числом прямих. Де Брейн[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], такі, що будь-які дві криві в сімействі або перетинаються в одній точці, або не перетинаються взагалі.

Див. також ред.

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

Примітки ред.

  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 // Discrete and Computational Geometry. — 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 // Discrete and Computational Geometry. — 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] — Indagationes Mathematicae. — 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. — Discrete and Computational Geometry. — 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 // SIAM Journal on Computing. — 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 // Mathematics Magazine. — 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 // Discrete and Computational Geometry. — 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) — ISBN 978-3-540-13722-1.
  • 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 // Discrete and Computational Geometry. — 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 // Discrete and Computational Geometry. — 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 // Discrete and Computational Geometry. — 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 // J. Reine Angew. Math.. — 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 // Combinatorics, Probability and Computing. — 1997. — Т. 6, вип. 3. — С. 353–358. — DOI:10.1017/S0963548397002976.
  • G. Tóth. Point sets with many k-sets // Discrete and Computational Geometry. — 2001. — Т. 26, вип. 2. — С. 187–194. — DOI:10.1007/s004540010022.

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Конфігурація_прямих&oldid=36766912