Configurație în linie dreaptă

O configurație de linii (sau o partiție a unui plan prin linii ) [1]  este o partiție a unui plan formată dintr-un set de linii . Configurațiile liniilor sunt studiate în geometria combinatorie , iar în geometria computațională , algoritmii sunt construiți pentru a construi configurații în mod eficient.

Definiție

Pentru orice mulțime A de drepte pe planul euclidian , se poate defini o relație de echivalență pe puncte ale planului, conform căreia două puncte p și q sunt echivalente dacă, pentru orice dreaptă l din A , fie p și q se află ambele pe linia l , sau se află în același semiplan deschis delimitat de linia dreaptă l . Dacă A este finit sau local finit [2] , clasele de echivalență ale acestor relații aparțin la trei grupe:

  1. interioare de poligoane convexe mărginite sau nemărginite ( celule de descompunere ), componente conexe ale unui subset de puncte din plan care nu se află pe niciuna dintre liniile din A ;
  2. segmente deschise și raze infinite deschise ( muchii de descompunere ), componente conexe ale punctelor unei singure drepte care nu aparțin nici unei alte linii din A ,
  3. puncte separate ( vârfuri ale partiției), intersecția a două sau mai multe linii din A .

Aceste trei tipuri de obiecte, legate între ele, formează o placă care acoperă planul. Se spune că două aranjamente de linii sunt izomorfe sau echivalente din punct de vedere combinator dacă există o corespondență unu-la-unu care păstrează adiacența între obiectele din partițiile de celule [3]

Complexitatea seturilor

Studiul configurațiilor de începuturi directe Jacob Steiner , care a dovedit prima limită asupra numărului maxim de elemente de diferite tipuri pe care o configurație le poate conține [4] [5] . O configurație de n linii are cel mult n ( n  − 1)/2 vârfuri, unul pe pereche de vârfuri care se intersectează. Acest maxim este atins pe configurații simple . O configurație se numește simplă dacă

1. nu se intersectează trei drepte într-un punct 2. nu există două drepte paralele.

În orice configurație vor exista n raze în jos infinite, una pe linie. Aceste raze separă n  + 1 celule ale partiției, care sunt nelimitate de jos. Toate celulele rămase au un singur vârf cel mai jos, [6] și fiecare astfel de vârf este cel mai mic pentru o singură celulă, astfel încât numărul de celule de partiție este egal cu numărul de vârfuri plus n  + 1 sau nu depășește n ( n  + 1)/2 + 1, vezi mai jos.numerele poligonale centrale . Numărul de muchii de partiție nu depășește n 2 , ceea ce poate fi văzut fie folosind caracteristica Euler , înlocuind numărul de vârfuri și celule, fie folosind observația că fiecare linie este împărțită în cel mult n muchii de alte n  - 1 linii. Din nou, cel mai rău caz în care se atinge granița sunt configurațiile simple ale liniilor.

Zona unei linii l într-un set de linii este un set de celule care au muchii situate pe l . Teorema zonei afirmă că numărul total de muchii din celulele unei singure zone este liniar. Mai precis, numărul total de margini de celule (din zona liniei) situate pe o parte a liniei l nu depășește 5 n  − 1 [7] [8] [9] , iar numărul total de margini de celule situate pe ambele părți ale lui l nu depășește [10] . Mai general, complexitatea totală a celulelor de partiție care sunt intersectate de o curbă convexă este O( n  α( n )), unde α denotă funcția Ackermann inversă , care poate fi arătată din secvențele Davenport-Schinzel [10] . Însumând complexitatea tuturor zonelor, se poate constata că suma complexității pătrate a celulelor din partiție este O( n 2 ) [11] .

Nivelul k al configurației liniilor este opolilinieformată din muchii care au exactklinii sub ea (adică, raza trasă în jos de la margine intersectează exactklinii), iarnivelul ≤k este toate configurațiile liniilor de piese sub nivelulk. Găsirea limitelor superioare și inferioare de complexitate pentruk-niveluri rămâne o problemă majoră deschisă în geometria discretă. Cea mai bună limită superioară este O(nk1/3), în timp ce cea mai bună limită inferioară este Ω(nexp(c(logk)1/2)) [12] [13] [14] . Se știe că complexitatea maximă a unui nivel ≤keste Θ(nk) [15] . Nivelul keste un caz special al unui drum monoton într-o partiție plană, adică o secvență de muchii care intersectează orice linie verticală într-un singur punct. Totuși, căile monotone pot fi mai complicate decâtk-nivele - există seturi de linii și căi monotone în aceste seturi, unde numărul de puncte în care calea își schimbă direcția este Ω(n2 − o(1)) [16] [17] .

Deși o singură celulă dintr-o partiție poate fi delimitată de toate n linii, în general nu este posibil ca m celule distincte să fie mărginite de n linii. În schimb, complexitatea totală a m celule este aproape egală cu Θ( m 2/3 n 2/3  +  n ) [18] [19] și aproape aceeași limită apare în teorema Szemerédy–Trotter asupra incidenței puncte și drepte în plan. O dovadă simplă a acestui fapt rezultă din inegalitatea numărului de intersecție  - dacă m celule au x  +  n muchii în total, puteți crea un grafic cu m vârfuri (unul pe celulă) și x muchii (una pe pereche de celule consecutive pe același linie) [20] [21] . Marginile acestui grafic pot fi desenate ca curbe care nu se intersectează în interiorul celulelor corespunzătoare vârfurilor de capăt ale muchiilor și apoi urmează liniile drepte ale mulțimii. Astfel, există O( n 2 ) intersecții în această figură. Totuși, prin inegalitatea numărului de intersecție, există intersecții Ω( x 3 / m 2 ). Pentru ca ambele inegalități să fie valabile, x trebuie să fie O( m 2/3 n 2/3 ) [22] .

Configurații proiective și dualitate proiectivă

Este adesea convenabil să studiezi configurația liniilor nu în spațiul euclidian, ci în planul proiectiv , deoarece în geometria proiectivă orice pereche de linii are un punct de intersecție. Pe un plan proiectiv, nu putem defini o partiție folosind laturile liniilor (o linie pe un plan proiectiv nu împarte planul în două laturi distincte), dar putem defini totuși celulele de partiție ca componente conectate ale punctelor care nu se află pe orice linie. Muchiile vor fi componente conectate constând din seturi de puncte aparținând unei singure linii, iar vârfurile vor fi puncte în care două sau mai multe linii se intersectează. Setul de linii din planul proiectiv diferă de omologul său euclidian, deoarece cele două raze euclidiene de pe ambele părți ale liniei sunt înlocuite cu o singură muchie în planul proiectiv, iar perechile de celule euclidiene nemărginite sunt înlocuite în planul proiectiv într-un singur celule.

Având în vedere dualitatea proiectivă , multe afirmații despre proprietățile combinatorii ale punctelor din plan pot fi înțelese mai simplu în forma duală echivalentă despre configurațiile liniilor. De exemplu, teorema lui Sylvester , care afirmă că orice set necoliniar de puncte din plan are o dreaptă simplă , care conține exact două puncte, devine, prin dualitate proiectivă, afirmația că orice configurație de drepte care are mai mult de un vârf are un simplu point , vârful la care toate cele două linii drepte. Cea mai veche demonstrație cunoscută a teoremei lui Sylvester de către Melchior ( Melchior (1940 )) folosește caracteristica lui Euler .

Triunghiuri în seturi de linii

Se spune că o configurație de linii în planul proiectiv este simplă dacă orice celulă a partiției este delimitată de exact trei muchii. Configurațiile simple au fost studiate pentru prima dată de Melchior [23] [24] . Sunt cunoscute trei familii infinite de seturi simple de linii:

  1. Un snop apropiat este format din n  - 1 linii care trec printr-un punct și o dreaptă care nu trece prin acest punct,
  2. Familia de drepte formată din laturile unui poligon regulat împreună cu axele de simetrie
  3. Laturile și axele de simetrie ale unui poligon uniform regulat, împreună cu o dreaptă la infinit.

În plus, există multe alte exemple de configurații simple simple care nu se încadrează în nicio familie infinită cunoscută [25] [24] . După cum scrie Grünbaum [24] , seturile simple de linii „apar ca exemple sau contraexemple în multe contexte de geometrie combinatorie și aplicațiile sale”. De exemplu, Artier, Grünbaum și Llibre [26] au folosit seturi simple de linii pentru a construi contraexemple pentru conjectura despre relația dintre puterile unui set de ecuații diferențiale și numărul de linii invariante pe care o ecuație le poate avea. Două contraexemple binecunoscute la conjectura Dirac-Motzkin (care afirmă că orice configurație de n linii are cel puțin n /2 puncte simple) sunt ambele simpliale [27] [28] [29] [30] .

Graficul dual al unei configurații de linie în care există un vârf pe celulă și o muchie care conectează vârfurile corespunzătoare celulelor cu o muchie comună în configurație este un cub parțial , un grafic în care vârfurile pot fi etichetate cu vectori de biți astfel încât distanța de pe grafic este egală cu distanța Hamming dintre semne. În cazul configurațiilor de linii, fiecare coordonată ia valoarea 0 pentru muchiile de pe o parte a liniei și 1 pentru muchiile de pe cealaltă parte [31] . Graficele duale ale configurațiilor simple au fost folosite pentru a construi familii infinite de cuburi parțiale regulate 3 izomorfe la graficele unui zonoedru simplu [32] .

De asemenea, este interesant să studiem numărul extrem de celule triunghiulare într-o configurație care nu este neapărat simplă. Orice configurație trebuie să aibă cel puțin n triunghiuri. Orice configurație cu numai n triunghiuri trebuie să fie simplă [25] [33] [34] . Se știe că numărul maxim posibil de triunghiuri într-o configurație simplă este mărginit de sus de numărul n ( n  − 1)/3, iar limita minimă este n ( n  − 3)/3. Limita inferioară este atinsă pe unele submulțimi ale diagonalelor unui 2 n -gon regulat [35] [25] . Pentru configurațiile non-simple, numărul maxim de triunghiuri este similar, dar mai sever limitat [36] [37] [38] . Problema triunghiului Cobon strâns legată cere numărul maxim de triunghiuri finite nesuprapuse (nu neapărat fețe) într-o configurație pe planul euclidian. Pentru unele, dar nu toate, valorile lui n , pot exista n ( n  - 2)/3 triunghiuri.

Placuri Multigrid și Penrose

Graficul dual al unei configurații simple de drepte poate fi reprezentat geometric ca un set de romburi , câte unul pe vârf al configurației, cu laturile perpendiculare pe liniile care se intersectează la vârf. Aceste romburi pot fi combinate pentru a forma o placare a unui poligon convex în cazul unei configurații cu un număr finit de linii, sau întregul plan în cazul configurațiilor local finite cu un număr infinit de linii. De Bruijn [39] a studiat cazuri speciale ale acestei construcții, în care configurația dreptelor constă din k seturi de drepte paralele cu distanță egală între ele. Pentru două familii perpendiculare de linii paralele, această construcție oferă pur și simplu parchetul pătrat familiar în plan, iar pentru trei familii de linii la 120 de grade una față de cealaltă (formând astfel o placare trihexagonală ), construcția dă o placare rombică . Cu toate acestea, pentru un număr mai mare de familii de linii, această construcție oferă plăci aperiodice . În special, pentru cinci familii de linii aflate în unghiuri egale între ele (sau, așa cum de Bruijn numește această configurație, o pentagrilă ), aceasta oferă o familie de plăci care include o versiune rombică a plăcilor Penrose .

O placă pătrată împărțită  este o configurație infinită de linii care formează o teselație periodică care seamănă cu o rețea multiplă cu patru familii paralele, dar în care două familii au o distanță mai mare între linii decât celelalte două și în care setul de linii este simplu. mai degrabă decât simplu. Tigla duală este plăcuța pătrată trunchiată . În mod similar, o placare triunghiulară este o configurație simplă infinită de linii cu trei familii de linii paralele, a cărei placare dublă este o placare hexagonală , iar o placare hexagonală divizată este o configurație simplă infinită de linii cu șase familii de linii paralele și două distanțe între linii în familii, care este duală cu placarea rombic-trihexagonală mare .

Algoritmi

Construirea unei configurații înseamnă calcularea reprezentării vârfurilor, muchiilor și celulelor unei configurații de linie (împreună cu relațiile acestora) atunci când se oferă o listă de linii dintr-un set, cum ar fi o listă de muchii dublu legată . Conform teoremei zonei, mulțimile pot fi construite eficient cu un algoritm incremental care adaugă o linie pe pas la setul de linii adăugate în pașii anteriori - fiecare linie nouă poate fi adăugată în timp proporțional cu zona sa, rezultând în timp O( n 2 ) [7] . Cu toate acestea, cerințele de memorie ale acestui algoritm sunt mari, așa că poate fi mai convenabil să enumerați toate proprietățile de configurare într-un algoritm care nu stochează toată configurația în memorie. Acest lucru poate fi realizat eficient în timp O( n 2 ) și spațiu O( n ) folosind o tehnică algoritmică cunoscută sub numele de balayage topologic [40] . Calculul precis al configurației liniei necesită o precizie de calcul de câteva ori mai mare decât datele de intrare (coordonate) - dacă linia este dată de două puncte pe ea, coordonatele configurației vârfurilor pot necesita de patru ori precizia punctelor de date de intrare. Prin urmare, algoritmii pentru construirea eficientă a configurațiilor cu acuratețe numerică limitată sunt de asemenea studiați în geometria computațională [41] [42] [43] .

Cercetătorii au studiat, de asemenea, algoritmi eficienți pentru construirea unor părți mai mici ale unei configurații, cum ar fi zone [44] , k -level [45] [46] [47] [48] sau un set de celule care conține un anumit set de puncte [49] [50] [51] . Problema găsirii unei configurații de vârfuri cu coordonate mediane x se pune (în formă duală) în statistica robustă ca problema calculării estimării Theil-Sen a unui set de puncte [52] .

Mark van Creveld a propus o problemă algoritmică de calculare a celei mai scurte căi dintre vârfuri într-o configurație de linii în care căile sunt mărginite de marginile configurației. Problema este pusă după cum urmează: există algoritmi care funcționează în mai puțin de un timp pătratic care ar fi cheltuit de algoritm pentru găsirea celei mai scurte căi într-un grafic de configurare complet [53] . Este cunoscut un algoritm de aproximare [54] , iar problema poate fi rezolvată eficient pentru liniile care sunt împărțite într-un număr mic de familii de linii paralele (ceea ce este tipic pentru străzile orașului) [55] , dar problema în general rămâne deschisă.

Variații și generalizări

Configurare pseudoline

O configurație de pseudolinii  este o configurație de curbe care au proprietăți topologice similare cu o configurație de linii [25] [56] . Ele pot fi definite cel mai simplu pe planul proiectiv ca simple curbe închise, dintre care oricare două se intersectează transversal într-un singur punct. Se spune că o configurație de pseudolinii este extensibilă dacă este echivalentă combinatoriu cu o configurație de linii. Problema distingerii multimilor rectificabile de nerectificabile [57] [58] este NP-complet . Orice configurație a unui număr finit de pseudolinii poate fi extinsă astfel încât pseudoliniile să devină linii într-o geometrie de incidență non-euclidiană , în care orice două puncte ale planului topologic sunt conectate printr-o singură linie (ca în planul euclidian), dar în pe care celelalte axiome ale geometriei euclidiene ar putea să nu le susțină.


Set inextensibil de nouă pseudolinii. (Toate colecțiile cu mai puțin de nouă pseudolinii sunt rectificabile.) Prin teorema lui Pappus , această configurație nu poate fi realizată în plan proiectiv peste niciun câmp.
Configurația hiperbolică a liniilor este echivalentă din punct de vedere combinator cu diagrama de coarde folosită de Ageev [59] pentru a demonstra că un grafic circular fără triunghiuri poate necesita uneori cinci culori .

avion Lobaciovski

Un alt tip de geometrie non-euclidiană este planul Lobachevsky , iar configurațiile liniilor hiperbolice din această geometrie au fost, de asemenea, studiate. Orice set finit de drepte din planul euclidian are o configurație echivalentă combinatoric în planul hiperbolic (de exemplu, înglobând vârfurile mulțimii într-un cerc mare și interpretând interiorul ciclului ca un model Klein al planului hiperbolic). Cu toate acestea, într-un set hiperbolic de linii este posibil să se evite intersecția liniilor fără cerința ca liniile să fie paralele. Graficul de intersecție cu linii în configurația hiperbolică este un grafic circular . Noțiunea corespunzătoare a unei configurații hiperbolice de linii pentru pseudolinii este o configurație slabă de pseudolinii [60] , o familie de curbe având aceleași proprietăți topologice ca și liniile [61] astfel încât oricare două curbe din familie fie se intersectează într-un punct, fie nu nu se intersectează deloc.

Vezi și

Note

  1. ↑ În literatura engleză , aranjament , care este adesea tradus ca configurație , există totuși un alt termen configurație , care este, de asemenea, tradus în mod natural ca și cuvântul configurație . Uneori se folosește termenul set de linii , uneori - partiție (prin linii sau hiperplane).
  2. ↑ În mulțimile local finite, orice submulțime mărginită a planului poate fi intersectată doar de un număr finit de drepte.
  3. ↑ Grünbaum, 1972 , p. patru.
  4. ↑ Steiner, 1826 .
  5. ↑ Agarwal, Sharir, 2000 .
  6. ↑ Pentru celulele care au o margine inferioară orizontală, selectați vârful din dreapta.
  7. ↑ 12 Chazelle et al, 1985 .
  8. ↑ Edelsbrunner, 1987 .
  9. ↑ Edelsbrunner, O'Rourke, Seidel, 1986 .
  10. ↑ 1 2 Berna, Eppstein, Plassman, Yao, 1991 .
  11. ↑ Aronov, Matousek, Sharir, 1994 .
  12. ↑ Dey, 1998 .
  13. ↑ Toth, 2001 .
  14. ↑ Problema limitării complexității k - nivelurilor a fost studiată pentru prima dată de Lovász (1971 ) și grupul lui Erdős, Simons, Straus ( Erdős et al (1973 )).
  15. ↑ Alon, Győri, 1986 .
  16. ↑ Balogh et al, 2004 .
  17. ↑ Matousek, 1991 .
  18. ↑ Canham, 1969 .
  19. ↑ Clarkson și colab., 1990 .
  20. ↑ Ajtai, Chvátal, Nou-născut, Szemerédi, 1982 .
  21. ↑ Leighton, 1983 .
  22. ↑ Szekely, 1997 .
  23. ↑ Melchior, 1940 .
  24. ↑ 1 2 3 Grünbaum, 2005 .
  25. ↑ 1 2 3 4 Grünbaum, 1972 .
  26. ↑ Artés, Grünbaum, Llibre, 1998 .
  27. ↑ Crowe, McKee, 1968 .
  28. ↑ Dirac, 1951 .
  29. ^ Kelly, Moser, 1958 .
  30. ↑ Grünbaum, 1972 , p. optsprezece.
  31. ↑ Eppstein, Falmagne, Ovchinnikov, 2007 .
  32. ↑ Eppstein, 2006 .
  33. ↑ Levi, 1926 .
  34. ↑ Roudneff, 1988 .
  35. ↑ Füredi, Palásti, 1984 .
  36. ↑ Purdy, 1979 .
  37. ↑ Purdy, 1980 .
  38. ↑ Strommer, 1977 .
  39. ↑ de Bruijn, 1981 .
  40. ↑ Edelsbrunner, Guibas, 1989 .
  41. ↑ Fortune, Milenkovic, 1991 .
  42. ↑ Greene, Yao, 1986 .
  43. ↑ Milenkovic, 1989 .
  44. ↑ Aharoni și colab., 1999 .
  45. ↑ Agarwal, de Berg, Matousek, Schwarzkopf, 1998 .
  46. ↑ Chan, 1999 .
  47. ↑ Cole, Sharir, Yap, 1987 .
  48. ↑ Edelsbrunner, Welzl, 1986 .
  49. ↑ Agarwal, 1990 .
  50. ↑ Agarwal, Matousek, Sharir, 1998 .
  51. ↑ Edelsbrunner, Guibas, Sharir, 1990 .
  52. ↑ Cole, Salowe, Steiger, Szemerédi, 1989 .
  53. ↑ Erickson, 1997 .
  54. ↑ Bose et al, 1996 .
  55. ^ Eppstein , Hart, 1999 .
  56. ↑ Agarwal, Sharir, 2002 .
  57. ↑ Shor, 1991 .
  58. ↑ Schaefer, 2010 .
  59. ↑ Ageev, 1996 .
  60. ↑ de Fraysseix, Ossona de Mendez, 2003 .
  61. ↑ Definiție alternativă a lui Shor (1991 ) - o pseudolinie este imaginea unei linii a unui homeomorfism plan .

Literatură

Link -uri