Rak linje konfiguration

En konfiguration av linjer (eller en partition av ett plan med linjer ) [1]  är en partition av ett plan som bildas av en uppsättning linjer . Linjekonfigurationer studeras i kombinatorisk geometri , och i beräkningsgeometri är algoritmer byggda för att konstruera konfigurationer effektivt.

Definition

För varje uppsättning A av linjer på det euklidiska planet kan man definiera en ekvivalensrelation på punkter i planet, enligt vilken två punkter p och q är ekvivalenta om, för någon linje l från A , antingen p och q båda ligger på linje l , eller så ligger de i samma öppna halvplan som begränsas av den räta linjen l . Om A är finit eller lokalt finit [2] tillhör ekvivalensklasserna för dessa relationer tre grupper:

  1. inre av avgränsade eller obegränsade konvexa polygoner ( nedbrytningsceller ) , sammankopplade komponenter i en delmängd av punkter i planet som inte finns på någon av linjerna från A ,
  2. öppna segment och öppna oändliga strålar ( nedbrytningskanter ), sammankopplade komponenter av punkter på en enda linje som inte tillhör någon annan linje från A ,
  3. separata punkter ( hörn av partitionen), skärningen av två eller flera linjer från A .

Dessa tre typer av föremål, sammankopplade, bildar en plattsättning som täcker planet. Två linjearrangemang sägs vara isomorfa eller kombinatoriskt ekvivalenta om det finns en en-till-en närliggande korrespondens mellan objekt i cellpartitioner [3]

Uppsättningarnas komplexitet

Studiet av konfigurationer av direkta början Jacob Steiner , som bevisade den första gränsen för det maximala antalet element av olika typer som en konfiguration kan innehålla [4] [5] . En konfiguration av n linjer har som mest n ( n  − 1)/2 hörn, en per par korsande hörn. Detta maximum uppnås på enkla konfigurationer . En konfiguration kallas enkel if

1. inga tre linjer skär varandra i en punkt 2. inga två linjer är parallella.

I vilken konfiguration som helst kommer det att finnas n oändliga nedåtriktade strålar, en per rad. Dessa strålar separerar n  + 1 celler i partitionen, som är obegränsade underifrån. Alla återstående celler har en enda lägsta vertex, [6] och varje sådan vertex är den lägre för en enskild cell, så antalet partitionsceller är lika med antalet hörn plus n  + 1 eller överstiger inte n ( n  + 1)/2 + 1, se nedan centrala polygonala tal . Antalet partitionskanter överstiger inte n 2 , vilket kan ses antingen genom att använda Euler-karakteristiken , ersätta antalet hörn och celler, eller genom att observera att varje linje är uppdelad i högst n kanter av andra n  − 1 linjer. Återigen, det värsta fallet där gränsen nås är enkla linjekonfigurationer.

Zonen för en linje l i en uppsättning linjer är en uppsättning celler som har kanter liggande på l . Zonsatsen säger att det totala antalet kanter i cellerna i en enskild zon är linjär. Närmare bestämt överstiger det totala antalet cellkanter (från linjens zon) på ena sidan av linjen l inte 5 n  − 1 [7] [8] [9] , och det totala antalet cellkanter som ligger på båda sidor av l överstiger inte [10] . Mer generellt är den totala komplexiteten för partitionscellerna som skärs av en konvex kurva O( n  α( n )), där α betecknar den omvända Ackermann-funktionen , som kan visas från Davenport–Schinzel-sekvenser [10] . När man summerar komplexiteten för alla zoner kan man finna att summan av den kvadratiska komplexiteten för cellerna i partitionen är O( n 2 ) [11] .

K-nivån för konfigurationen av linjer är enpolylinjesom bildas av kanter som har exaktkandra linjer under sig (det vill säga strålen som dras ner från kanten skär exaktklinjer), och≤k-nivån är alla detaljlinjekonfigurationer underk-nivån. Att hitta övre och nedre komplexitetsgränser förk-nivåer förblir ett stort öppet problem inom diskret geometri. Den bästa övre gränsen är O(nk1/3), medan den bästa nedre gränsen är Ω(nexp(c(logk)1/2)) [12] [13] [14] . Det är känt att den maximala komplexiteten för en ≤k-nivå är Θ(nk) [15] . K-nivån är ett specialfall av en monoton bana i en plan partition, det vill säga en sekvens av kanter som skär en vertikal linje i en enda punkt. Men monotona banor kan vara mer komplicerade änk-nivåer - det finns uppsättningar av linjer och monotona banor i dessa uppsättningar, där antalet punkter där banan ändrar riktning är Ω(n2 − o(1)) [16] [17] .

Även om en enskild cell i en partition kan begränsas av alla n linjer, är det i allmänhet inte möjligt för m distinkta celler att begränsas av n linjer. Omvänt är den totala komplexiteten för m celler nästan lika med Θ( m 2/3 n 2/3  +  n ) [18] [19] och nästan samma gräns visas i Szemerédy–Trotters sats om incidensen av punkter och linjer i planet. Ett enkelt bevis på detta faktum följer av skärningstalet olikhet  - om m celler har x  +  n kanter totalt kan du skapa en graf med m hörn (en per cell) och x kanter (en per par på varandra följande celler på samma linje) [20] [21] . Kanterna på denna graf kan ritas som kurvor som inte korsar inuti cellerna som motsvarar kanternas ändpunkter, och sedan följer de raka linjerna i uppsättningen. Det finns alltså O( n 2 ) skärningspunkter i denna figur. Men genom skärningstalets olikhet finns det Ω( x 3 / m 2 ) skärningspunkter. För att båda olikheterna ska gälla måste x vara O( m 2/3 n 2/3 ) [22] .

Projektiva konfigurationer och projektiv dualitet

Det är ofta bekvämt att studera konfigurationen av linjer inte i det euklidiska rummet, utan i det projektiva planet , eftersom i projektiv geometri har vilket linjepar som helst en skärningspunkt. På ett projektivt plan kan vi inte definiera en partition med hjälp av sidorna av linjer (en linje på ett projektivt plan delar inte planet i två distinkta sidor), men vi kan fortfarande definiera partitionsceller som sammankopplade komponenter av punkter som inte ligger på vilken rad som helst. Kanter kommer att vara sammankopplade komponenter som består av uppsättningar av punkter som tillhör en enda linje, och hörn kommer att vara punkter där två eller flera linjer skär varandra. Uppsättningen av linjer i det projektiva planet skiljer sig från dess euklidiska motsvarighet, eftersom de två euklidiska strålarna på båda sidor av linjen ersätts av en enda kant i det projektiva planet, och par av obundna euklidiska celler ersätts i det projektiva planet till enstaka linjer. celler.

Med tanke på projektiv dualitet kan många påståenden om kombinatoriska egenskaper hos punkter i planet enklare förstås i den ekvivalenta dubbla formen om linjekonfigurationer. Till exempel, Sylvesters teorem , som säger att alla icke-kollinjära punkter i planet har en enkel linje , som innehåller exakt två punkter, blir, genom projektiv dualitet, påståendet att varje konfiguration av linjer som har mer än en vertex har en enkel punkt , toppunkten där alla två räta linjer. Det tidigaste kända beviset för Sylvesters teorem av Melchior ( Melchior (1940 )) använder Euler-egenskapen .

Trianglar i raduppsättningar

En konfiguration av linjer i det projektiva planet sägs vara enkel om någon cell i partitionen är begränsad av exakt tre kanter. Enkla konfigurationer studerades först av Melchior [23] [24] . Tre oändliga familjer av enkla uppsättningar av linjer är kända:

  1. En nära-kärve består av n  − 1 linjer som går genom en punkt och en linje som inte går genom denna punkt,
  2. Linjefamiljen som bildas av sidorna av en vanlig polygon tillsammans med symmetriaxlarna
  3. Sidor och symmetriaxlar för en jämn regelbunden polygon, tillsammans med en linje i oändligheten.

Dessutom finns det många andra exempel på enkla enkla konfigurationer som inte passar in i någon känd oändlig familj [25] [24] . Som Grünbaum [24] skriver , enkla uppsättningar av linjer "uppstår som exempel eller motexempel i många sammanhang av kombinatorisk geometri och dess tillämpningar". Till exempel använde Artier, Grünbaum och Llibre [26] enkla uppsättningar av linjer för att konstruera motexempel till gissningarna om förhållandet mellan styrkorna hos en uppsättning differentialekvationer och antalet invarianta linjer en ekvation kan ha. Två välkända motexempel till Dirac-Motzkin-förmodan (som säger att varje konfiguration av n linjer har minst n /2 enkla punkter) är båda förenklade [27] [28] [29] [30] .

Den dubbla grafen för en linjekonfiguration där det finns en vertex per cell och en kant som förbinder de hörn som motsvarar celler med en gemensam kant i konfigurationen är en partiell kub , en graf där hörnen kan märkas med bitvektorer så att avståndet på grafen är lika med Hamming-avståndet mellan märkena. I fallet med linjekonfigurationer tar varje koordinat värdet 0 för kanter på ena sidan av linjen och 1 för kanter på den andra sidan [31] . De dubbla graferna av enkla konfigurationer har använts för att konstruera oändliga familjer av 3-regelbundna partiella kuber som är isomorfa till grafer av en enkel zonohedron [32] .

Det är också intressant att studera det extrema antalet triangulära celler i en konfiguration som inte nödvändigtvis är enkel. Alla konfigurationer måste ha minst n trianglar. Varje konfiguration med endast n trianglar måste vara enkel [25] [33] [34] . Det är känt att det maximalt möjliga antalet trianglar i en enkel konfiguration begränsas ovanifrån av talet n ( n  − 1)/3, och den minsta gränsen är n ( n  − 3)/3. Den nedre gränsen nås på vissa delmängder av diagonalerna för en regelbunden 2 n -gon [35] [25] . För icke-enkla konfigurationer är det maximala antalet trianglar liknande men mer strängt begränsat [36] [37] [38] . Det närbesläktade Cobon-triangelproblemet frågar efter det maximala antalet icke-överlappande ändliga trianglar (inte nödvändigtvis ansikten) i en konfiguration på det euklidiska planet. För vissa, men inte alla, värden på n kan det finnas n ( n  − 2)/3 trianglar.

Multigrid och Penrose plattsättningar

Den dubbla grafen för en enkel konfiguration av linjer kan representeras geometriskt som en uppsättning romber , en per konfigurationspunkt, med sidor vinkelräta mot linjerna som skär varandra i vertexen. Dessa romber kan kombineras för att bilda en plattsättning av en konvex polygon i fallet med en konfiguration med ett ändligt antal linjer, eller hela planet i fallet med lokalt ändliga konfigurationer med ett oändligt antal linjer. De Bruijn [39] studerade speciella fall av denna konstruktion, där konfigurationen av linjer består av k uppsättningar av parallella linjer med lika avstånd från varandra. För två vinkelräta familjer av parallella linjer ger denna konstruktion helt enkelt den välbekanta fyrkantiga parketten i planet, och för tre familjer av linjer i 120 graders vinkel mot varandra (som bildar en trihexagonal plattsättning ) ger konstruktionen en rombisk plattsättning . Men för ett större antal familjer av linjer ger denna konstruktion aperiodiska plattsättningar . Speciellt för fem familjer av linjer i lika vinklar mot varandra (eller, som de Bruijn kallar denna konfiguration, en pentagrid ), ger detta en familj av plattsättningar som inkluderar en rombisk version av Penrose plattsättningar .

En delad kvadratisk  plattsättning är en oändlig konfiguration av linjer som bildar en periodisk tessellation som liknar ett multirutnät med fyra parallella familjer, men där två familjer har större avstånd mellan linjerna än de andra två, och där uppsättningen av linjer är enkel snarare än enkelt. Den dubbla plattsättningen är den trunkerade kvadratiska plattsättningen . På liknande sätt är en triangulär plattsättning en oändlig enkel konfiguration av linjer med tre familjer av parallella linjer, vars dubbla plattsättning är en hexagonal plattsättning och en delad sexkantig plattsättning är en oändlig enkel konfiguration av linjer med sex familjer av parallella linjer och två avstånd mellan linjer i familjerna, vilket är dubbelt med den stora rombisk-trihexagonala plattsättningen .

Algoritmer

Att konstruera en konfiguration innebär att beräkna representationen av hörn, kanter och celler i en linjekonfiguration (tillsammans med deras relationer) när de ges en lista med linjer i en uppsättning, till exempel en dubbellänkad lista med kanter . Enligt zonsatsen kan mängder byggas effektivt med en inkrementell algoritm som lägger till en rad per steg till uppsättningen rader som lagts till i tidigare steg – varje ny rad kan läggas till i tid proportionell mot sin zon, vilket resulterar i tiden O( n 2 ) [7] . Minneskraven för denna algoritm är dock höga, så det kan vara bekvämare att räkna upp alla konfigurationsegenskaper i en algoritm som inte lagrar all konfiguration i minnet. Detta kan göras effektivt i O( n 2 ) tid och O( n ) rymd med hjälp av en algoritmisk teknik som kallas topologisk balayage [40] . Noggrann beräkning av linjekonfigurationen kräver beräkningsnoggrannhet flera gånger större än indata (koordinater) - om linjen ges av två punkter på den, kan koordinaterna för vertexkonfigurationen kräva fyra gånger noggrannheten hos indatapunkterna. Därför studeras algoritmer för att effektivt konstruera konfigurationer med begränsad numerisk noggrannhet också i beräkningsgeometri [41] [42] [43] .

Forskarna studerade också effektiva algoritmer för att konstruera mindre delar av en konfiguration, såsom zoner [44] , k -nivåer [45] [46] [47] [48] eller en uppsättning celler som innehåller en given uppsättning punkter [49] [50] [51] . Problemet med att hitta en konfiguration av hörn med median x - koordinater uppstår (i en dubbel form) i robust statistik som problemet med att beräkna Theil-Sen uppskattningen av en uppsättning punkter [52] .

Mark van Creveld föreslog ett algoritmiskt problem med att beräkna den kortaste vägen mellan hörn i en konfiguration av linjer där banorna begränsas av konfigurationens kanter. Problemet ställs på följande sätt: finns det några algoritmer som fungerar på mindre än en kvadratisk tid som skulle spenderas av algoritmen för att hitta den kortaste vägen i en komplett konfigurationsgraf [53] . En approximationsalgoritm är känd [54] , och problemet kan effektivt lösas för linjer som är uppdelade i ett litet antal familjer av parallella linjer (vilket är typiskt för stadsgator) [55] , men problemet i allmänhet förblir öppet.

Variationer och generaliseringar

Pseudolinkonfiguration

En konfiguration av pseudoliner  är en konfiguration av kurvor som har liknande topologiska egenskaper som en konfiguration av linjer [25] [56] . De kan enklast definieras på det projektiva planet som enkla slutna kurvor, av vilka två som helst skär tvärs över i en enda punkt. En konfiguration av pseudoliner sägs vara töjbar om den är kombinatoriskt ekvivalent med en konfiguration av linjer. Problemet med att skilja likriktbara från icke likriktbara uppsättningar [57] [58] är NP-komplett . Vilken konfiguration som helst av ett ändligt antal pseudoliner kan utökas så att pseudolinerna blir linjer i en icke-euklidisk infallsgeometri , där två punkter på det topologiska planet är sammankopplade med en enda linje (som i det euklidiska planet), men i vilket de andra axiomen för euklidisk geometri kanske inte håller.


Otöjbar uppsättning av nio pseudoliner. (Alla samlingar med mindre än nio pseudoliner är likriktbara.) Enligt Pappus' teorem kan denna konfiguration inte realiseras i det projektiva planet över något fält.
Den hyperboliska konfigurationen av linjer är kombinatoriskt ekvivalent med ackorddiagrammet som används av Ageev [59] för att bevisa att en cirkelgraf utan trianglar ibland kan kräva fem färger .

Lobachevsky plan

En annan typ av icke-euklidisk geometri är Lobachevsky-planet , och konfigurationer av hyperboliska linjer i denna geometri har också studerats. Vilken ändlig uppsättning linjer som helst i det euklidiska planet har en kombinatoriskt ekvivalent konfiguration i det hyperboliska planet (till exempel omsluter mängdens hörn i en stor cirkel och tolkar det inre av cykeln som en Klein-modell av det hyperboliska planet). I en hyperbolisk uppsättning linjer är det dock möjligt att undvika skärningspunkten mellan linjer utan krav på att linjerna är parallella. Linjeskärningsgrafen i hyperbolisk konfiguration är en cirkelgraf . Motsvarande uppfattning om en hyperbolisk konfiguration av linjer för pseudoliner är en svag konfiguration av pseudoliner [60] , en familj av kurvor som har samma topologiska egenskaper som linjer [61] så att vilka två kurvor som helst i familjen antingen skär varandra i en punkt eller gör inte skära alls.

Se även

Anteckningar

  1. ↑ I engelsk litteratur , arrangemang , som ofta översätts som konfiguration , finns det dock en annan term konfiguration , som också naturligt översätts som ordet konfiguration . Ibland används termen raduppsättning , ibland - partition (efter linjer eller hyperplan).
  2. ↑ I lokalt ändliga mängder kan alla avgränsade delmängder av planet endast skäras av ett ändligt antal linjer.
  3. ↑ Grünbaum, 1972 , sid. fyra.
  4. ↑ Steiner, 1826 .
  5. ↑ Agarwal, Sharir, 2000 .
  6. ↑ För celler som har en horisontell bottenkant, välj vertex till höger.
  7. ↑ 12 Chazelle et al, 1985 .
  8. ↑ Edelsbrunner, 1987 .
  9. ↑ Edelsbrunner, O'Rourke, Seidel, 1986 .
  10. ↑ 1 2 Bern, Eppstein, Plassman, Yao, 1991 .
  11. ↑ Aronov, Matousek, Sharir, 1994 .
  12. ↑ Dey, 1998 .
  13. ↑ Toth, 2001 .
  14. ↑ Problemet med att begränsa komplexiteten hos k -nivåer studerades först av Lovász (1971 ) och gruppen 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 et al, 1990 .
  20. ↑ Ajtai, Chvátal, Newborn, 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 , sid. arton.
  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 et al, 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. ↑ Schäfer, 2010 .
  59. ↑ Ageev, 1996 .
  60. ↑ de Fraysseix, Ossona de Mendez, 2003 .
  61. ↑ Alternativ definition av Shor (1991 ) - en pseudolin är bilden av en linje av en plan homeomorphism .

Litteratur

Länkar