Konfigurace s přímkou

Konfigurace čar (neboli rozdělení roviny čarami ) [1]  je rozdělení roviny tvořené množinou čar . Konfigurace čar jsou studovány v kombinatorické geometrii a ve výpočetní geometrii jsou algoritmy sestaveny tak, aby konfigurace konstruovaly efektivně.

Definice

Pro libovolnou množinu A přímek na euklidovské rovině lze definovat vztah ekvivalence na bodech roviny, podle kterého jsou dva body p a q ekvivalentní, jestliže pro libovolnou přímku l z A leží oba p a q na přímka l , nebo leží ve stejné otevřené polorovině ohraničené přímkou ​​l . Je-li A konečné nebo lokálně konečné [2] , třídy ekvivalence těchto vztahů patří do tří skupin:

  1. vnitřky ohraničených nebo neohraničených konvexních polygonů ( rozkladové buňky ), spojených složek podmnožiny bodů v rovině, které nejsou obsaženy na žádné z čar z A ,
  2. otevřené úsečky a otevřené nekonečné paprsky ( rozkladné hrany ), spojené složky bodů jedné přímky, které nepatří žádné jiné přímce z A ,
  3. samostatné body ( vrcholy přepážky), průsečík dvou nebo více čar z A .

Tyto tři typy objektů, spojené dohromady, tvoří obklad , který pokrývá rovinu. Dvě řádková uspořádání jsou považována za izomorfní nebo kombinatoricky ekvivalentní , pokud existuje vzájemná korespondence zachovávající sousedství mezi objekty v buněčných oddílech [3].

Složitost množin

Studium konfigurací přímých počátků Jacob Steiner , který dokázal první vazbu na maximální počet prvků různých typů, které může konfigurace obsahovat [4] [5] . Konfigurace n čar má nejvýše n ( n  − 1)/2 vrcholů, jeden na pár protínajících se vrcholů. Tohoto maxima je dosaženo u jednoduchých konfigurací . Konfigurace se nazývá jednoduchá if

1. žádné tři přímky se neprotínají v jednom bodě 2. žádné dvě přímky nejsou rovnoběžné.

V jakékoli konfiguraci bude n nekonečných paprsků směřujících dolů, jeden na řádek. Tyto paprsky oddělují n  + 1 buněk přepážky, které jsou zespodu neohraničené. Všechny zbývající buňky mají jeden nejnižší vrchol [6] a každý takový vrchol je nižší pro jednu buňku, takže počet buněk rozdělení se rovná počtu vrcholů plus n  + 1 nebo nepřesahuje n ( n  + 1)/2 + 1, viz níže centrální polygonální čísla . Počet předělovacích hran nepřesahuje n 2 , což lze vidět buď pomocí Eulerovy charakteristiky , dosazením počtu vrcholů a buněk, nebo pomocí pozorování, že každý řádek je rozdělen na nejvýše n hran dalšími n  − 1 řádky. Opět platí, že nejhorším případem, kdy je hranice dosaženo, jsou jednoduché konfigurace vedení.

Zóna přímky l v množině čar je množina buněk, které mají hrany ležící na l . Zónová věta říká, že celkový počet hran v buňkách jedné zóny je lineární. Přesněji řečeno, celkový počet hran buněk (od zóny čáry) umístěných na jedné straně čáry l nepřesahuje 5 n  − 1 [7] [8] [9] , a celkový počet hran buněk ležících na obou stranách l nepřesahuje [10] . Obecněji řečeno, celková složitost buněk oddílu, které protíná konvexní křivka, je O( n  α( n )), kde α označuje inverzní Ackermannovu funkci , kterou lze ukázat z Davenport–Schinzelových sekvencí [10] . Shrneme-li složitost všech zón, lze zjistit, že součet druhé mocniny složitosti buněk v oddílu je O( n 2 ) [11] .

K-úroveň konfigurace čar jekřivkatvořená hranami, které mají pod sebou přesněkdalších čar (to znamená, že paprsek tažený dolů od hrany protíná přesněkčar) a≤k-úroveň je všechny konfigurace linky dílů podk. Nalezení horní a dolní hranice složitosti prok-úrovně zůstává hlavním otevřeným problémem v diskrétní geometrii. Nejlepší horní mez je O(nk1/3), zatímco nejlepší dolní mez je Ω(nexp(c(logk)1/2)) [12] [13] [14] . Je známo, že maximální složitost a ≤k-úrovně je Θ(nk) [15] . Úroveň kje speciální případ monotónní cesty v rovinném rozdělení, to znamená posloupnost hran protínajících jakoukoli svislou čáru v jediném bodě. Monotónní cesty však mohou být složitější nežk-úrovně - v těchto množinách jsou množiny čar a monotónní cesty, kde počet bodů, ve kterých cesta mění směr, je Ω(n2 − o(1)) [16] [17] .

Ačkoli jedna buňka v oddílu může být ohraničena všemi n řádky, není obecně možné, aby m různých buněk bylo ohraničeno n řádky. Naopak celková složitost m buněk je téměř rovna Θ( m 2/3 n 2/3  +  n ) [18] [19] a téměř stejná hranice se objevuje v Szemerédy-Trotterově teorému o výskytu body a čáry v rovině. Jednoduchý důkaz této skutečnosti vyplývá z průsečíkové číselné nerovnosti  - pokud má m buněk celkem x  +  n hran, můžete vytvořit graf s m vrcholy (jeden na buňku) a x hranami (jeden na dvojici po sobě jdoucích buněk na stejné řádek) [20] [21] . Hrany tohoto grafu lze nakreslit jako křivky, které se neprotínají uvnitř buněk odpovídajících koncovým vrcholům hran, a pak následovat přímé linie množiny. Na tomto obrázku je tedy O( n 2 ) průsečíků. Při nerovnosti čísel průsečíků však existují průsečíky Ω( x 3 / m 2 ). Aby obě nerovnosti platily, x musí být O( m 2/3 n 2/3 ) [22] .

Projektivní konfigurace a projektivní dualita

Často je vhodné studovat konfiguraci čar ne v euklidovském prostoru, ale v projektivní rovině , protože v projektivní geometrii má každá dvojice čar průsečík. Na projektivní rovině nemůžeme definovat oddíl pomocí stran úseček (přímka na projektivní rovině nerozděluje rovinu na dvě odlišné strany), ale stále můžeme definovat buňky oddílu jako spojené součásti bodů, které neleží na jakýkoli řádek. Hrany budou spojené komponenty sestávající z množin bodů patřících jedné přímce a vrcholy budou body, kde se protínají dvě nebo více čar. Sada čar v projektivní rovině se liší od svého euklidovského protějšku, protože dva euklidovské paprsky na obou stranách přímky jsou nahrazeny jednou hranou v projektivní rovině a dvojice neohraničených euklidovských buněk jsou nahrazeny v projektivní rovině do jediné. buňky.

Vzhledem k projektivní dualitě lze mnohá tvrzení o kombinatorických vlastnostech bodů v rovině jednodušeji chápat v ekvivalentní duální formě o liniových konfiguracích. Například Sylvesterův teorém , který říká, že každá nekolineární množina bodů v rovině má jednoduchou úsečku obsahující právě dva body, se projektivní dualitou stává tvrzením, že jakákoli konfigurace přímek, která má více než jeden vrchol, má jednoduchý bod , vrchol, ve kterém jsou všechny dvě přímky. Nejčasnější známý důkaz Sylvesterovy věty Melchior ( Melchior (1940 )) používá Eulerovu charakteristiku .

Trojúhelníky v sadách čar

Konfigurace čar v projektivní rovině je jednoduchá , pokud je jakákoli buňka přepážky ohraničena přesně třemi hranami. Jednoduché konfigurace poprvé studoval Melchior [23] [24] . Jsou známy tři nekonečné rodiny jednoduchých sad čar:

  1. Blízký svazek se skládá z n  − 1 čar procházejících jedním bodem a jedné přímky, která tímto bodem neprochází,
  2. Rodina čar tvořených stranami pravidelného mnohoúhelníku spolu s osami symetrie
  3. Strany a osy symetrie sudého pravidelného mnohoúhelníku spolu s přímkou ​​v nekonečnu.

Kromě toho existuje mnoho dalších příkladů jednoduchých jednoduchých konfigurací , které nezapadají do žádné známé nekonečné rodiny [25] [24] . Jak píše Grünbaum [24] , jednoduché sady čar „se objevují jako příklady nebo protipříklady v mnoha kontextech kombinatorické geometrie a jejích aplikací“. Například Artier, Grünbaum a Llibre [26] použili jednoduché sady čar ke konstrukci protipříkladů k domněnce o vztahu mezi mocninami množiny diferenciálních rovnic a počtem invariantních čar, které rovnice může mít. Dva dobře známé protipříklady k Dirac-Motzkinově domněnce (které tvrdí, že jakákoli konfigurace n čar má alespoň n /2 jednoduchých bodů) jsou oba jednoduché [27] [28] [29] [30] .

Duální graf čárové konfigurace, ve které je jeden vrchol na buňku a jedna hrana spojující vrcholy odpovídající buňkám se společnou hranou v konfiguraci, je částečná krychle , graf, ve kterém mohou být vrcholy označeny bitovými vektory tak, že vzdálenost na grafu je rovna Hammingově vzdálenosti mezi značkami. V případě liniových konfigurací nabývá každá souřadnice hodnotu 0 pro hrany na jedné straně úsečky a 1 pro hrany na druhé straně [31] . Duální grafy jednoduchých konfigurací byly použity ke konstrukci nekonečných rodin 3-pravidelných parciálních krychlí izomorfních ke grafům jednoduchého zonohedru [32] .

Je také zajímavé studovat extrémní počty trojúhelníkových buněk v konfiguraci, která nemusí být nutně jednoduchá. Každá konfigurace musí mít alespoň n trojúhelníků. Jakákoli konfigurace s pouze n trojúhelníky musí být jednoduchá [25] [33] [34] . Je známo, že maximální možný počet trojúhelníků v jednoduché konfiguraci je shora ohraničen číslem n ( n  − 1)/3 a minimální hranice je n ( n  − 3)/3. Spodní hranice je dosažena na některých podmnožinách úhlopříček pravidelného 2 n -úhelníku [35] [25] . Pro nejednoduché konfigurace je maximální počet trojúhelníků podobný, ale přísněji omezený [36] [37] [38] . Úzce související problém Cobonova trojúhelníku se ptá na maximální počet nepřekrývajících se konečných trojúhelníků (ne nutně ploch) v konfiguraci na euklidovské rovině. Pro některé, ale ne pro všechny hodnoty n , může existovat n ( n  − 2)/3 trojúhelníků.

Obklady Multigrid a Penrose

Dvojitý graf jednoduché konfigurace čar může být reprezentován geometricky jako soubor kosočtverců , jeden na vrchol konfigurace, se stranami kolmými k čarám, které se ve vrcholu protínají. Tyto kosočtverce lze kombinovat tak, aby vytvořily dlaždici konvexního mnohoúhelníku v případě konfigurace s konečným počtem čar nebo celou rovinu v případě lokálně konečných konfigurací s nekonečným počtem čar. De Bruijn [39] studoval speciální případy této konstrukce, ve kterých konfigurace čar sestává z k sad rovnoběžných čar se stejnou vzdáleností od sebe. Pro dvě na sebe kolmé rodiny rovnoběžných linií tato konstrukce jednoduše dává známé čtvercové parkety v rovině a pro tři rodiny linií o 120 stupních vůči sobě (takže tvoří trihexagonální obklad ), konstrukce dává kosočtvercový obklad . Pro větší počet rodin linek však tato konstrukce dává aperiodické obklady . Konkrétně pro pět rodin linií ve stejných úhlech vůči sobě (nebo, jak de Bruijn nazývá tuto konfiguraci, pentagrid ), to dává rodinu obkladů, která zahrnuje kosočtvercovou verzi Penroseových obkladů .

Dlaždice rozděleného čtverce  je nekonečná konfigurace čar, které tvoří periodickou mozaiku, která se podobá multimřížce se čtyřmi paralelními rodinami, ale ve které mají dvě rodiny větší vzdálenost mezi čarami než ostatní dvě, a ve které je sada čar jednoduchá. spíše než jednoduché. Dvojitý obklad je komolý čtvercový obklad . Podobně je trojúhelníkový obklad nekonečnou jednoduchou konfigurací čar se třemi rodinami rovnoběžných čar, jejichž duální obklad je šestihranný obklad , a dělený hexagonální obklad je nekonečně jednoduchá konfigurace čar se šesti rodinami rovnoběžných čar a dvěma vzdálenosti mezi čarami v rodinách, což je dvojí s velkým kosočtvercovým-trihexagonálním obkladem .

Algoritmy

Konstrukce konfigurace znamená výpočet reprezentace vrcholů, hran a buněk čárové konfigurace (spolu s jejich vztahy), když je uveden seznam čar v sadě, jako je například dvojitě propojený seznam hran . Podle zónového teorému lze množiny efektivně sestavit pomocí přírůstkového algoritmu, který přidá jeden řádek na krok k množině řádků přidaných v předchozích krocích – každý nový řádek lze přidat v čase úměrně jeho zóně, což má za následek čas O( n 2 ) [7] . Paměťové požadavky tohoto algoritmu jsou však vysoké, takže může být vhodnější vyjmenovat všechny konfigurační vlastnosti v algoritmu, který neukládá celou konfiguraci do paměti. To lze efektivně provést v čase O( n 2 ) a prostoru O ( n ) pomocí algoritmické techniky známé jako topologické balayage [40] . Přesný výpočet konfigurace čáry vyžaduje přesnost výpočtu několikanásobně větší než vstupní data (souřadnice) - pokud je čára dána dvěma body na ní, mohou souřadnice konfigurace vrcholu vyžadovat čtyřnásobnou přesnost vstupních datových bodů. Proto jsou algoritmy pro efektivní konstrukci konfigurací s omezenou numerickou přesností studovány také ve výpočetní geometrii [41] [42] [43] .

Výzkumníci také studovali účinné algoritmy pro konstrukci menších částí konfigurace, jako jsou zóny [44] , k -úrovně [45] [46] [47] [48] nebo sada buněk obsahujících danou sadu bodů [49]. [50] [51] . Problém nalezení konfigurace vrcholů se středními x - ovými souřadnicemi vyvstává (v duální podobě) v robustní statistice jako problém výpočtu Theil-Senova odhadu množiny bodů [52] .

Mark van Creveld navrhl algoritmický problém výpočtu nejkratší cesty mezi vrcholy v konfiguraci čar, kde jsou cesty ohraničeny hranami konfigurace. Problém je položen následovně: existují nějaké algoritmy, které fungují za méně než kvadratický čas, který by algoritmus strávil hledáním nejkratší cesty v kompletním konfiguračním grafu [53] . Je znám aproximační algoritmus [54] a problém lze efektivně vyřešit pro čáry, které jsou rozděleny do malého počtu rodin rovnoběžných čar (což je typické pro městské ulice) [55] , ale problém obecně zůstává otevřený.

Variace a zobecnění

Pseudoline konfigurace

Konfigurace pseudočar  je konfigurace křivek , které mají podobné topologické vlastnosti jako konfigurace čar [25] [56] . Nejjednodušeji je lze definovat na projektivní rovině jako jednoduché uzavřené křivky, z nichž se libovolné dvě protínají příčně v jediném bodě. O konfiguraci pseudolinií se říká, že je rozšiřitelná , pokud je kombinatoricky ekvivalentní konfiguraci linek. Problém rozlišení rektifikovatelných od nerektifikovatelných množin [57] [58] je NP-úplný . Libovolná konfigurace konečného počtu pseudolinií může být rozšířena tak, že se z pseudolinií stanou linie v neeuklidovské incidenční geometrii , ve které jsou libovolné dva body topologické roviny spojeny jedinou linkou (jako v euklidovské rovině), ale v což ostatní axiomy euklidovské geometrie nemusí platit.


Nerozšiřitelná sada devíti pseudolinií. (Všechny kolekce s méně než devíti pseudočarami jsou rektifikovatelné.) Podle Pappusova teorému nelze tuto konfiguraci realizovat v projektivní rovině přes žádné pole.
Hyperbolická konfigurace čar je kombinatoricky ekvivalentní akordickému diagramu používanému Ageevem [59] k prokázání, že kruhový graf bez trojúhelníků může někdy vyžadovat pět barev .

Lobačevského letadlo

Dalším typem neeuklidovské geometrie je Lobachevského rovina a byly také studovány konfigurace hyperbolických čar v této geometrii. Jakákoli konečná množina čar v euklidovské rovině má kombinatoricky ekvivalentní konfiguraci v hyperbolické rovině (například uzavírá vrcholy množiny do velkého kruhu a interpretuje vnitřek cyklu jako Kleinův model hyperbolické roviny). V hyperbolické množině čar je však možné vyhnout se průniku čar bez požadavku, aby byly přímky rovnoběžné. Graf průsečíku čar v hyperbolické konfiguraci je kruhový graf . Odpovídající představa hyperbolické konfigurace čar pro pseudočáry je slabá konfigurace pseudočar [60] , rodina křivek majících stejné topologické vlastnosti jako čáry [61] , takže libovolné dvě křivky v rodině se buď protínají v jednom bodě, nebo se vůbec neprotínají.

Viz také

Poznámky

  1. ↑ V anglické literatuře , uspořádání , což se často překládá jako konfigurace , existuje však i jiný výraz configuration , který se také přirozeně překládá jako slovo konfigurace . Někdy se používá termín sada čar , někdy - rozdělení (po čarách nebo nadrovinách).
  2. ↑ V lokálně konečných množinách může být jakákoliv ohraničená podmnožina roviny protnuta pouze konečným počtem čar.
  3. ↑ Grünbaum, 1972 , s. čtyři.
  4. ↑ Steiner, 1826 .
  5. ↑ Agarwal, Sharir, 2000 .
  6. ↑ U buněk, které mají vodorovný spodní okraj, vyberte vrchol vpravo.
  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, Matoušek, Sharir, 1994 .
  12. ↑ Dey, 1998 .
  13. ↑ Toth, 2001 .
  14. ↑ Problémem omezení složitosti k -úrovní se poprvé zabýval Lovász (1971 ) a skupina Erdős, Simons, Straus ( Erdős et al (1973 )).
  15. ↑ Alon, Győri, 1986 .
  16. ↑ Balogh et al, 2004 .
  17. ↑ Matoušek, 1991 .
  18. ↑ Canham, 1969 .
  19. ↑ Clarkson a kol., 1990 .
  20. ↑ Ajtai, Chvátal, Novorozenec, 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. osmnáct.
  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, Matoušek, Schwarzkopf, 1998 .
  46. ↑ Chan, 1999 .
  47. ↑ Cole, Sharir, Yap, 1987 .
  48. ↑ Edelsbrunner, Welzl, 1986 .
  49. ↑ Agarwal, 1990 .
  50. ↑ Agarwal, Matoušek, Sharir, 1998 .
  51. ↑ Edelsbrunner, Guibas, Sharir, 1990 .
  52. ↑ Cole, Salowe, Steiger, Szemerédi, 1989 .
  53. ↑ Erickson, 1997 .
  54. ↑ Bose a kol., 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. ↑ Alternativní definice Shora (1991 ) - pseudočára je obrazem čáry rovinného homeomorfismu .

Literatura

Odkazy