Lige linje konfiguration

En konfiguration af linjer (eller en opdeling af et plan med linjer ) [1]  er en opdeling af et plan dannet af et sæt linjer . Linjekonfigurationer studeres i kombinatorisk geometri , og i beregningsgeometri er algoritmer bygget til at konstruere konfigurationer effektivt.

Definition

For ethvert sæt A af linjer på det euklidiske plan kan man definere en ækvivalensrelation på punkter i planen, ifølge hvilken to punkter p og q er ækvivalente, hvis, for en linje l fra A , enten p og q begge ligger på linje l , eller de ligger i samme åbne halvplan afgrænset af den rette linje l . Hvis A er endelig eller lokalt endelig [2] , tilhører ækvivalensklasserne for disse relationer tre grupper:

  1. indre af afgrænsede eller uafgrænsede konvekse polygoner ( nedbrydningsceller ) , forbundne komponenter af en delmængde af punkter i planet, der ikke er indeholdt på nogen af ​​linjerne fra A ,
  2. åbne segmenter og åbne uendelige stråler ( nedbrydningskanter ), forbundne komponenter af punkter på en enkelt linje, der ikke tilhører nogen anden linje fra A ,
  3. separate punkter ( hjørner af partitionen), skæringspunktet mellem to eller flere linjer fra A .

Disse tre typer objekter, forbundet med hinanden, danner en flisebelægning , der dækker planet. To liniearrangementer siges at være isomorfe eller kombinatorisk ækvivalente, hvis der er en en-til-en naboskabsbevarende overensstemmelse mellem objekter i cellepartitioner [3]

Kompleksiteten af ​​sæt

Studiet af konfigurationer af direkte begyndelse Jacob Steiner , som beviste den første grænse for det maksimale antal elementer af forskellige typer, som en konfiguration kan indeholde [4] [5] . En konfiguration af n linjer har højst n ( n  − 1)/2 toppunkter, en pr. par af skærende hjørner. Dette maksimum nås ved simple konfigurationer . En konfiguration kaldes simpel if

1. ingen tre linjer skærer hinanden i et punkt 2. ikke to linjer er parallelle.

I enhver konfiguration vil der være n uendelige nedadgående stråler, en pr. linje. Disse stråler adskiller n  + 1 celler i partitionen, som er ubegrænsede nedefra. Alle resterende celler har et enkelt laveste toppunkt, [6] og hvert sådant toppunkt er det nederste for en enkelt celle, så antallet af partitionsceller er lig med antallet af toppunkter plus n  + 1 eller overstiger ikke n ( n  + 1)/2 + 1, se nedenfor centrale polygonale tal . Antallet af partitionskanter overstiger ikke n 2 , hvilket kan ses enten ved at bruge Euler-karakteristikken , der erstatter antallet af hjørner og celler, eller ved at bruge den observation, at hver linje er opdelt i højst n kanter af andre n  − 1 linjer. Igen, det værste tilfælde, hvor grænsen nås, er simple linjekonfigurationer.

Zonen af ​​en linje l i et sæt linjer er et sæt celler, der har kanter liggende på l . Zonesætningen siger, at det samlede antal kanter i cellerne i en enkelt zone er lineær. Mere præcist overstiger det samlede antal cellekanter (fra linjens zone) placeret på den ene side af linjen l ikke 5 n  − 1 [7] [8] [9] , og det samlede antal cellekanter liggende på begge sider af l ikke overstiger [10] . Mere generelt er den samlede kompleksitet af partitionscellerne, der skæres af en konveks kurve, O( n  α( n )), hvor α betegner den omvendte Ackermann-funktion , som kan vises fra Davenport-Schinzel-sekvenser [10] . Opsummerer kompleksiteten af ​​alle zoner, kan det konstateres, at summen af ​​den kvadrerede kompleksitet af cellerne i partitionen er O( n 2 ) [11] .

K-niveauet af konfigurationen af ​​linjer er enpolylinjedannet af kanter, der har nøjagtigtkandre linjer under sig (det vil sige, at strålen, der trækkes ned fra kanten, skærer nøjagtigtklinjer), og≤k-niveauet er alle delelinjekonfigurationer underkniveauet. At finde øvre og nedre kompleksitetsgrænser fork-niveauer er fortsat et stort åbent problem i diskret geometri. Den bedste øvre grænse er O(nk1/3), mens den bedste nedre grænse er Ω(nexp(c(logk)1/2)) [12] [13] [14] . Det er kendt, at den maksimale kompleksitet af et ≤k-niveau er Θ(nk) [15] . K-niveauet er et specialtilfælde af en monoton sti i en plan partition, det vil sige en sekvens af kanter, der skærer enhver lodret linje i et enkelt punkt. Montone baner kan dog være mere komplicerede endk-niveauer - der er sæt af linjer og monotone baner i disse sæt, hvor antallet af punkter, hvor stien ændrer retning er Ω(n2 − o(1)) [16] [17] .

Selvom en enkelt celle i en partition kan være afgrænset af alle n linjer, er det generelt ikke muligt for m distinkte celler at være afgrænset af n linjer. Omvendt er den totale kompleksitet af m celler næsten lig med Θ( m 2/3 n 2/3  +  n ) [18] [19] og næsten den samme grænse optræder i Szemerédy-Trotter-sætningen om forekomsten af punkter og linjer i planet. Et simpelt bevis for denne kendsgerning følger af skæringstallet ulighed  - hvis m celler har x  +  n kanter i alt, kan du lave en graf med m hjørner (én pr. celle) og x kanter (en pr. par af på hinanden følgende celler på samme linje) [20] [21] . Kanterne på denne graf kan tegnes som kurver, der ikke skærer hinanden inde i cellerne, der svarer til kanternes endespidser, og følger derefter sættets lige linjer. Der er således O( n 2 ) skæringspunkter i denne figur. Men ved skæringstallets ulighed er der Ω( x 3 / m 2 ) skæringspunkter. For at begge uligheder skal holde, skal x være O( m 2/3 n 2/3 ) [22] .

Projektive konfigurationer og projektiv dualitet

Det er ofte praktisk at studere konfigurationen af ​​linjer ikke i det euklidiske rum, men i det projektive plan , da ethvert linjepar i projektiv geometri har et skæringspunkt. På et projektivt plan kan vi ikke definere en partition ved hjælp af siderne af linjer (en linje på et projektivt plan deler ikke planet i to adskilte sider), men vi kan stadig definere partitionsceller som forbundne komponenter af punkter, der ikke ligger på enhver linje. Kanter vil være forbundne komponenter bestående af sæt af punkter, der tilhører en enkelt linje, og toppunkter vil være punkter, hvor to eller flere linjer skærer hinanden. Sættet af linjer i det projektive plan adskiller sig fra dets euklidiske modstykke, da de to euklidiske stråler på begge sider af linjen er erstattet af en enkelt kant i det projektive plan, og par af ubundne euklidiske celler erstattes i det projektive plan til enkelte celler.

I lyset af projektiv dualitet kan mange påstande om kombinatoriske egenskaber af punkter i planet lettere forstås i den tilsvarende dobbelte form om linjekonfigurationer. For eksempel bliver Sylvesters teorem , der siger, at ethvert ikke-kollineært sæt af punkter i planet har en simpel linje , der indeholder præcis to punkter, ved projektiv dualitet, udsagnet om, at enhver konfiguration af linjer, der har mere end ét toppunkt, har en simpel punkt , toppunktet, hvor alle to rette linjer. Det tidligste kendte bevis for Sylvesters sætning af Melchior ( Melchior (1940 )) bruger Euler-karakteristikken .

Trekanter i sæt af linjer

En konfiguration af linjer i det projektive plan siges at være enkel , hvis en celle i skillevæggen er afgrænset af nøjagtigt tre kanter. Simple konfigurationer blev først undersøgt af Melchior [23] [24] . Tre uendelige familier af simple sæt af linjer er kendt:

  1. En nær-skive består af n  − 1 linjer, der går gennem et punkt og en linje, der ikke går gennem dette punkt,
  2. Familien af ​​linjer dannet af siderne af en regulær polygon sammen med symmetriakserne
  3. Sider og symmetriakser af en jævn regulær polygon sammen med en uendelig linje.

Derudover er der mange andre eksempler på enkelte simple konfigurationer , der ikke passer ind i nogen kendt uendelig familie [25] [24] . Som Grünbaum [24] skriver , optræder simple sæt af linjer "som eksempler eller modeksempler i mange sammenhænge med kombinatorisk geometri og dens anvendelser". For eksempel brugte Artier, Grünbaum og Llibre [26] simple sæt af linjer til at konstruere modeksempler til formodningen om forholdet mellem potenserne af et sæt differentialligninger og antallet af invariante linjer en ligning kan have. To velkendte modeksempler til Dirac-Motzkin-formodningen (som siger, at enhver konfiguration af n linjer har mindst n /2 simple punkter) er begge simple [27] [28] [29] [30] .

Den dobbelte graf for en linjekonfiguration, hvor der er et toppunkt pr. celle og en kant, der forbinder hjørnerne svarende til celler med en fælles kant i konfigurationen, er en delvis terning , en graf, hvor hjørnerne kan mærkes med bitvektorer , således at afstanden på grafen er lig med Hamming-afstanden mellem mærker. I tilfælde af linjekonfigurationer tager hver koordinat værdien 0 for kanter på den ene side af linjen og 1 for kanter på den anden side [31] . De dobbelte grafer af simple konfigurationer er blevet brugt til at konstruere uendelige familier af 3-regulære partielle terninger, som er isomorfe til grafer af et simpelt zonohedron [32] .

Det er også interessant at studere det ekstreme antal af trekantede celler i en konfiguration, der ikke nødvendigvis er enkel. Enhver konfiguration skal have mindst n trekanter. Enhver konfiguration med kun n trekanter skal være enkel [25] [33] [34] . Det er kendt, at det maksimalt mulige antal trekanter i en simpel konfiguration er afgrænset ovenfra af tallet n ( n  − 1)/3, og minimumsgrænsen er n ( n  − 3)/3. Den nedre grænse nås på nogle delmængder af diagonalerne af en regulær 2 n - gon [35] [25] . For ikke-simple konfigurationer er det maksimale antal trekanter ens, men mere alvorligt begrænset [36] [37] [38] . Det nært beslægtede Cobon -trekantproblem beder om det maksimale antal ikke-overlappende endelige trekanter (ikke nødvendigvis flader) i en konfiguration på det euklidiske plan. For nogle, men ikke alle, værdier af n kan der være n ( n  − 2)/3 trekanter.

Multigrid og Penrose flisebelægninger

Den dobbelte graf af en simpel konfiguration af linjer kan repræsenteres geometrisk som et sæt rhombuses , en pr. vertex af konfigurationen, med sider vinkelret på linjerne, der skærer i toppunktet. Disse romber kan kombineres til at danne en flisebelægning af en konveks polygon i tilfælde af en konfiguration med et endeligt antal linjer, eller hele planet i tilfælde af lokalt endelige konfigurationer med et uendeligt antal linjer. De Bruijn [39] studerede særlige tilfælde af denne konstruktion, hvor konfigurationen af ​​linjer består af k sæt parallelle linjer med lige stor afstand fra hinanden. For to vinkelrette familier af parallelle linjer giver denne konstruktion blot den velkendte firkantede parket i planet, og for tre familier af linjer i 120 grader i forhold til hinanden (derved danner en trihexagonal flisebelægning ) giver konstruktionen en rombisk flisebelægning . Men for et større antal familier af linjer giver denne konstruktion aperiodiske fliser . Især for fem familier af linjer med lige store vinkler i forhold til hinanden (eller, som de Bruijn kalder denne konfiguration, en pentagrid ), giver dette en familie af flisebelægninger, der inkluderer en rombisk version af Penrose-fliser .

En delt kvadratisk  flisebelægning er en uendelig konfiguration af linjer, der danner en periodisk tessellation, der ligner et multigitter med fire parallelle familier, men hvor to familier har større afstand mellem linjer end de to andre, og hvor linjesættet er simpelt. snarere end simpelt. Den dobbelte flisebelægning er den afkortede firkantede flisebelægning . Tilsvarende er en trekantet flisebelægning en uendelig enkel konfiguration af linjer med tre familier af parallelle linjer, hvis dobbelte flisebelægning er en hexagonal flisebelægning , og en delt hexagonal flisebelægning er en uendelig enkel konfiguration af linjer med seks familier af parallelle linjer og to afstande mellem linjer i familierne, hvilket er dobbelt med den store romb-trihexagonale flisebelægning .

Algoritmer

At konstruere en konfiguration betyder at beregne repræsentationen af ​​hjørnerne, kanterne og cellerne i en linjekonfiguration (sammen med deres relationer), når der gives en liste over linjer i et sæt, såsom en dobbeltforbundet liste over kanter . Ifølge zonesætningen kan mængder bygges effektivt med en trinvis algoritme, der tilføjer en linje pr. trin til det sæt af linjer, der er tilføjet i tidligere trin - hver ny linje kan tilføjes i tid proportionalt med dens zone, hvilket resulterer i tiden O( n 2 ) [7] . Imidlertid er hukommelseskravene for denne algoritme høje, så det kan være mere praktisk at opregne alle konfigurationsegenskaber i en algoritme, der ikke gemmer hele konfigurationen i hukommelsen. Dette kan gøres effektivt i O( n 2 ) tid og O( n ) rum ved hjælp af en algoritmisk teknik kendt som topologisk balayage [40] . Nøjagtig beregning af linjekonfigurationen kræver beregningsnøjagtighed flere gange større end inputdataene (koordinaterne) - hvis linjen er givet af to punkter på den, kan koordinaterne for toppunktets konfiguration kræve fire gange nøjagtigheden af ​​inputdatapunkterne. Derfor studeres algoritmer til at konstruere konfigurationer effektivt med begrænset numerisk nøjagtighed også i beregningsgeometri [41] [42] [43] .

Forskerne studerede også effektive algoritmer til at konstruere mindre dele af en konfiguration, såsom zoner [44] , k -niveauer [45] [46] [47] [48] eller et sæt celler, der indeholder et givet sæt punkter [49] [50] [51] . Problemet med at finde en konfiguration af toppunkter med median x - koordinater opstår (i en dobbelt form) i robust statistik som problemet med at beregne Theil-Sen-estimatet af et sæt punkter [52] .

Mark van Creveld foreslog et algoritmisk problem med at beregne den korteste vej mellem toppunkter i en konfiguration af linjer, hvor stierne er afgrænset af konfigurationens kanter. Problemet er stillet som følger: er der nogen algoritmer, der virker på mindre end en kvadratisk tid, som ville blive brugt af algoritmen på at finde den korteste vej i en komplet konfigurationsgraf [53] . En tilnærmelsesalgoritme er kendt [54] , og problemet kan effektivt løses for linjer, der er opdelt i et lille antal familier af parallelle linjer (hvilket er typisk for bygader) [55] , men problemet forbliver generelt åbent.

Variationer og generaliseringer

Pseudolinkonfiguration

En konfiguration af pseudoliner  er en konfiguration af kurver , der har lignende topologiske egenskaber som en konfiguration af linjer [25] [56] . De kan enklest defineres på det projektive plan som simple lukkede kurver, hvoraf to vilkårlige skærer tværgående i et enkelt punkt. En konfiguration af pseudoliner siges at være udvidelsesbar , hvis den er kombinatorisk ækvivalent med en konfiguration af linjer. Problemet med at skelne rektificerbare fra ikke-korrigerbare sæt [57] [58] er NP-komplet . Enhver konfiguration af et endeligt antal pseudoliner kan udvides, så pseudolinerne bliver til linjer i en ikke-euklidisk indfaldsgeometri , hvor to punkter på det topologiske plan er forbundet med en enkelt linje (som i det euklidiske plan), men i som de andre aksiomer i euklidisk geometri måske ikke holder.


Uudvideligt sæt med ni pseudoliner. (Alle samlinger med mindre end ni pseudoliner er retificerbare.) Ved Pappus' sætning kan denne konfiguration ikke realiseres i det projektive plan over noget felt.
Den hyperbolske konfiguration af linjer er kombinatorisk ækvivalent med akkorddiagrammet brugt af Ageev [59] for at bevise, at en cirkelgraf uden trekanter nogle gange kan kræve fem farver .

Lobachevsky fly

En anden type ikke-euklidisk geometri er Lobachevsky-planet , og konfigurationer af hyperbolske linjer i denne geometri er også blevet undersøgt. Ethvert endeligt sæt linjer i det euklidiske plan har en kombinatorisk ækvivalent konfiguration i det hyperbolske plan (for eksempel ved at omslutte mængdens toppunkter i en storcirkel og fortolke det indre af cyklussen som en Klein-model af det hyperbolske plan). Men i et hyperbolsk sæt af linjer er det muligt at undgå skæringen af ​​linjer uden krav om, at linjerne skal være parallelle. Linjeskæringsgrafen i den hyperbolske konfiguration er en cirkelgraf . Den tilsvarende forestilling om en hyperbolsk konfiguration af linjer for pseudoliner er en svag konfiguration af pseudoliner [60] , en familie af kurver med de samme topologiske egenskaber som linjer [61] , således at to vilkårlige kurver i familien enten skærer hinanden i et punkt eller gør skærer overhovedet ikke.

Se også

Noter

  1. ↑ I engelsk litteratur er arrangement , som ofte oversættes med konfiguration , dog er der et andet udtryk konfiguration , som også naturligt oversættes med ordet konfiguration . Nogle gange bruges udtrykket sæt af linjer , nogle gange - partition (efter linjer eller hyperplaner).
  2. ↑ I lokalt endelige mængder kan enhver afgrænset delmængde af planet kun skæres af et begrænset antal linjer.
  3. ↑ Grünbaum, 1972 , s. fire.
  4. ↑ Steiner, 1826 .
  5. ↑ Agarwal, Sharir, 2000 .
  6. ↑ For celler, der har en vandret bundkant, skal du vælge toppunktet til højre.
  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 at begrænse kompleksiteten af ​​k -niveauer blev først undersøgt af Lovász (1971 ) og gruppen af ​​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, Nyfødt, 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 , s. atten.
  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 af Shor (1991 ) - en pseudolin er billedet af en linje af en plan homeomorfisme .

Litteratur

Links