Uspořádání čar - Arrangement of lines

v geometrie an uspořádání řádků je rozdělit z letadlo tvořený sbírkou řádky. Meze složitosti uspořádání byly studovány v diskrétní geometrie, a výpočetní geometry našli algoritmy pro efektivní konstrukci uspořádání.
Definice
Pro jakoukoli sadu A řádků v Euklidovské letadlo, lze definovat vztah ekvivalence na body roviny, podle kterých dva body p a q jsou ekvivalentní, pokud pro každý řádek l z A, buď p a q jsou oba zapnuté l nebo oba patří ke stejnému otevřenému polorovina ohraničen l. Když A je konečný nebo místně konečný[1] the třídy ekvivalence tohoto vztahu jsou tři typy:
- interiéry ohraničených nebo neohraničených konvexních polygonů (dále jen buňky ujednání), připojené komponenty podmnožiny roviny, která není obsažena v žádné z řádků A,
- otevřené úsečky a otevřené nekonečné paprsky ( hrany uspořádání), připojené součásti bodů jedné linie, které nepatří k žádným dalším liniím A, a
- jednotlivé body ( vrcholy uspořádání), průsečíky dvou nebo více řádků A.
Tyto tři typy objektů se spojují a tvoří a buněčný komplex zakrývající letadlo. Říká se, že existují dvě ujednání izomorfní nebo kombinačně ekvivalentní pokud existuje vzájemná korespondence zachovávající sousedství mezi objekty v jejich přidružených komplexech buněk.[2]
Složitost uspořádání
Studium uspořádání bylo zahájeno Jakob Steiner, který prokázal první meze maximálního počtu funkcí různých typů, které může uspořádání mít.[3]Ujednání s n řádků má maximálně n(n − 1)/2 vrcholy, jeden na pár křížení čar. Toto maximum je dosaženo pro jednoduchá opatřeníty, ve kterých má každá dvě linie odlišnou dvojici křížení. V jakémkoli uspořádání bude n paprsky nekonečného dolů, jeden na řádek; tyto paprsky se oddělují n + 1 buňky uspořádání, které jsou neohraničené směrem dolů. Zbývající buňky všechny mají jedinečný nejspodnější vrchol,[4] a každý vrchol je nejspodnější pro jedinečnou buňku, takže počet buněk v uspořádání je počet vrcholů plus n + 1 nebo maximálně n(n + 1) / 2 + 1; vidět sekvence líného kuchaře. Počet okrajů uspořádání je maximálně n2, jak je patrné z použití Eulerova charakteristika vypočítat to z počtu vrcholů a buněk nebo pozorováním, že každý řádek je rozdělen nanejvýš n hranami n - 1 řádek; této nejhorší možné meze je opět dosaženo u jednoduchých uspořádání.
The zóna řádku l v liniovém uspořádání je sbírka buněk majících hrany patřící k l. The věta o zóně uvádí, že celkový počet hran v buňkách jedné zóny je lineární. Přesněji, celkový počet okrajů buněk náležejících k jedné straně čáry l je maximálně 5n − 1,[5] a celkový počet okrajů buněk patřících oběma stranám l je nanejvýš .[6] Obecněji je celková složitost buněk uspořádání řádků, které jsou protínány jakoukoli konvexní křivkou, O (n α (n)), kde α označuje inverzní Ackermannova funkce, jak může být zobrazeno pomocí Sekvence Davenport – Schinzel.[6] Sečtením složitosti všech zón zjistíme, že součet čtverců komplexů buněk v uspořádání je O (n2).[7]
The k-úroveň uspořádání je polygonální řetězec tvořený hranami, které mají přesně k další řádky přímo pod nimi a ≤k úroveň je část uspořádání pod k-úroveň. Nalezení shodných horních a dolních mezí pro složitost a k-úroveň 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 Ω (n exp (C (logk)1/2)).[8] Naproti tomu maximální složitost ≤k-úroveň je známa jako Θ (nk).[9] A k-úroveň je speciální případ monotónní cesty v uspořádání; to je posloupnost hran, která protíná jakoukoli svislou čáru v jednom bodě. Monotónní cesty však mohou být mnohem komplikovanější než k-úrovně: v těchto uspořádáních existují uspořádání a monotónní cesty, kde počet bodů, ve kterých cesta mění směr, je Ω (n2 - o (1)).[10]
Ačkoli může být jedna buňka v uspořádání ohraničena všemi n řádky, to obecně není možné pro m různé buňky, aby všechny byly ohraničeny n řádky. Spíše celková složitost m buněk je maximálně Θ (m2/3n2/3 + n),[11] téměř stejná vazba, jaká se vyskytuje v Szemerédi – Trotterova věta na bodové výskyty v rovině. Jednoduchý důkaz toho vyplývá z nerovnost křížení čísel:[12] -li m buňky mají celkem X + n hran, lze vytvořit graf s m uzly (jeden na buňku) a X hrany (jeden na pár po sobě jdoucích buněk na stejné linii). Okraje tohoto grafu lze nakreslit jako křivky, které neprotínají buňky odpovídající jejich koncovým bodům, a poté následovat čáry uspořádání; proto existují O (n2) přechody na tomto výkresu. Avšak nerovností čísla přechodu existuje Ω (X3/m2) přechody; za účelem uspokojení obou mezí, X musí být O (m2/3n2/3).[13]
Projektivní uspořádání a projektivní dualita
Často je vhodné studovat uspořádání linií ne v euklidovské rovině, ale v projektivní rovina, vzhledem k tomu, že v projektivní geometrii má každá dvojice čar průsečík. V projektivní rovině již nemůžeme definovat uspořádání pomocí stran čar (čára v projektivní rovině nerozdělí rovinu na dvě odlišné strany), ale stále můžeme definovat buňky uspořádání, aby byly spojenými komponentami body, které nepatří k žádné linii, hrany, které mají být spojenými komponentami sad bodů patřících k jedné linii, a vrcholy jako body, kde se protínají dvě nebo více linií. Uspořádání čar v projektivní rovině se liší od svého euklidovského protějšku v tom, že dva euklidovské paprsky na obou koncích čáry jsou nahrazeny jediným okrajem v projektivní rovině, který spojuje vrcholy nejvíce vlevo a vpravo na této linii a v těchto párech neomezené euklidovské buňky jsou nahrazeny v projektivní rovině jednotlivými buňkami, které jsou v nekonečnu překročeny projektivní linií.
Kvůli projektivní dualita mnoho výroků o kombinatorických vlastnostech bodů v rovině lze snáze pochopit v ekvivalentní dvojí formě o uspořádání přímek. Například Věta Sylvester – Gallai s tím, že jakákoli nekolineární sada bodů v rovině má obyčejná linka obsahující přesně dva body, transformuje se pod projektivní dualitou na tvrzení, že jakékoli uspořádání přímek s více než jedním vrcholem má obyčejný bod, vrchol, kde se protínají pouze dvě čáry. Nejdříve známý důkaz věty o Sylvestrovi-Gallai, podle Melchior (1940), používá Eulerova charakteristika ukázat, že takový vrchol musí vždy existovat.
Trojúhelníky v uspořádání

Uspořádání čar v projektivní rovině se říká zjednodušený pokud je každá buňka uspořádání ohraničena přesně třemi hranami; jednoduchá opatření nejprve studoval Melchior.[14] Jsou známy tři nekonečné rodiny jednoduchých liniových uspořádání:
- A téměř tužka skládající se z n - 1 vedení jedním bodem spolu s jedním dalším řádkem, který neprojde stejným bodem,
- Rodina linií tvořená stranami a pravidelný mnohoúhelník společně s jeho osy symetrie, a
- Strany a osy symetrie rovnoměrného pravidelného mnohoúhelníku spolu s přímkou v nekonečnu.
Kromě toho existuje mnoho dalších příkladů sporadická zjednodušená opatření které se nehodí do žádné známé nekonečné rodiny.[15]Jako Grünbaum[16] píše, zjednodušená uspořádání „se objevují jako příklady nebo protiklady v mnoha kontextech kombinatorické geometrie a jejích aplikací.“ Například, Artés, Grünbaum & Llibre (1998) použít zjednodušená uspořádání k vytvoření protipříkladů domněnky o vztahu mezi stupněm množiny diferenciální rovnice a počet invariantních čar, které rovnice mohou mít. Dva známé protiklady k Dirac – Motzkinova domněnka (který uvádí, že jakýkoli n-řádkové uspořádání má alespoň n/ 2 obyčejné body) jsou oba zjednodušující.[17]
The duální graf uspořádání řádků, ve kterém je jeden uzel na buňku a jeden okraj spojující jakoukoli dvojici buněk, které sdílejí okraj uspořádání, je částečná kostka, graf, ve kterém lze uzly označit bitvektory takovým způsobem, aby se vzdálenost grafu rovnala Hammingova vzdálenost mezi štítky; v případě liniového uspořádání přiřadí každá souřadnice označení 0 uzlům na jedné straně jedné z linek a 1 uzlům na druhé straně.[18] Duální grafy zjednodušených uspořádání byly použity ke konstrukci nekonečných rodin 3-pravidelné dílčí kostky, izomorfní s grafy jednoduchá zonohedra.[19]
Je také zajímavé studovat extrémní počty trojúhelníkových buněk v uspořádáních, která nemusí být nutně jednoduchá. V jakémkoli uspořádání musí existovat alespoň n trojúhelníky; každé uspořádání, které má pouze n trojúhelníky musí být jednoduché.[20] Je známo, že maximální možný počet trojúhelníků v jednoduchém uspořádání je horně ohraničen n(n - 1) / 3 a spodní ohraničený n(n - 3) / 3; dolní hranice je dosažena určitými podmnožinami úhlopříček pravidelné 2n-gon.[21] U jednoduchých uspořádání je maximální počet trojúhelníků podobný, ale pevněji ohraničený.[22] Úzce související Kobonův trojúhelníkový problém požaduje maximální počet nepřekrývajících se konečných trojúhelníků (nikoli nutně ploch) v uspořádání v euklidovské rovině; pro některé, ale ne všechny hodnoty n, n(n - 2) / 3 trojúhelníky jsou možné.
Multigrids a Penroseovy obklady
Duální graf jednoduchého liniového uspořádání může být reprezentován geometricky jako soubor kosočtverec, jedna na vrchol uspořádání, se stranami kolmými k přímkám, které se v daném vrcholu setkávají. Tyto kosočtverce mohou být spojeny dohromady a vytvořit tak obklad a konvexní mnohoúhelník v případě uspořádání konečně mnoha linek, nebo celé roviny v případě lokálně konečného uspořádání s nekonečně mnoha liniemi. de Bruijn (1981) zkoumali speciální případy této konstrukce, ve kterých se sestava vedení skládá k sady rovnoměrně rozmístěných rovnoběžných čar. Pro dvě kolmé rodiny paralelních linií tato konstrukce dává jen známé čtvercové obklady roviny a pro tři rodiny linií ve 120stupňových úhlech od sebe (samy tvoří a trihexagonal obklady ) toto produkuje kosočtverečný obklad. Pro více rodin linek však tato konstrukce produkuje neperiodické obklady. Zejména pro pět rodin linií ve stejných úhlech k sobě navzájem (nebo, jak toto uspořádání nazývá de Bruijn, a Pentagrid) produkuje rodinu obkladů, které zahrnují kosočtverečnou verzi Penroseovy obklady.
The čtvercový obklad tetrakis je nekonečné uspořádání řádků tvořících periodický obklad, který se podobá multižáru se čtyřmi paralelními rodinami, ale ve kterém jsou dvě z rodin více rozloženy než ostatní dvě a ve kterém je uspořádání spíše jednoduché než jednoduché. Jeho duální je zkrácený čtvercový obklad. Podobně trojúhelníkové obklady je nekonečné zjednodušené uspořádání řádků se třemi paralelními rodinami, které má dvojí funkci šestihranný obklad a půlený šestihranný obklad je nekonečné jednoduché uspořádání řádků se šesti paralelními rodinami a dvěma řádky, dvojími k skvělé rhombitrihexagonální obklady.
Algoritmy
Konstruování prostředek uspořádání, daný jako vstup, seznam linií v uspořádání, výpočet reprezentace vrcholů, hran a buněk uspořádání spolu s sousedstvími mezi těmito objekty, například jako dvojnásobně spojený seznam hran. Kvůli teorému o zóně lze uspořádání efektivně zkonstruovat pomocí přírůstkového algoritmu, který přidává po jednom řádku k uspořádání dříve přidaných řádků: každá nová linka může být přidána v čase úměrném její zóně, což má za následek celkovou dobu výstavby z O (n2).[5] Požadavky na paměť tohoto algoritmu jsou však vysoké, takže může být pohodlnější ohlásit všechny funkce uspořádání algoritmem, který nezachová celé uspořádání v paměti najednou. To může být opět provedeno efektivně, v čase O (n2) a prostor O (n), o algoritmická technika známý jako topologické zametání.[23] Výpočet uspořádání řádků přesně vyžaduje číselnou přesnost několikrát větší než přesnost vstupních souřadnic: pokud je čára zadána dvěma body na ní, souřadnice vrcholů uspořádání mohou vyžadovat čtyřikrát větší přesnost než tyto vstupní body. Proto výpočetní geometři také studovali algoritmy pro efektivní konstrukci uspořádání s omezenou numerickou přesností.[24]
Vědci také studovali efektivní algoritmy pro konstrukci menších částí uspořádání, jako jsou zóny,[25] k-úrovně,[26] nebo sada buněk obsahující danou sadu bodů.[27] Problém nalezení vrcholu uspořádání s mediánem X-koordinát vznikne (v duální formě) v robustní statistiky jako problém výpočtu Theil – Sen odhadce množiny bodů.[28]
Marc van Kreveld navrhl algoritmický problém výpočtu nejkratší cesty mezi vrcholy v liniovém uspořádání, kde jsou cesty omezeny tak, aby sledovaly okraje uspořádání, rychleji než kvadratický čas, který by trvalo použití algoritmu nejkratší cesty na celý graf uspořádání.[29] An aproximační algoritmus je známo,[30] a problém lze efektivně vyřešit u linií, které spadají do malého počtu paralelních rodin (jak je typické pro městské uliční sítě),[31] ale obecný problém zůstává otevřený.
Neeuklidovské uspořádání vedení


A uspořádání pseudolinu je rodina křivky sdílejí podobné topologické vlastnosti s řádkovým uspořádáním.[32] Ty lze nejjednodušší definovat v projektivní rovina tak jako jednoduché uzavřené křivky kterékoli dva z nich se setkávají na jednom přechodu.[33] Říká se, že pseudolinové uspořádání je roztažitelný pokud je kombinatoricky ekvivalentní liniovému uspořádání; to je kompletní pro existenciální teorie skutečností rozlišit roztažitelná uspořádání od neroztažitelných.[34] Každé uspořádání konečně mnoha pseudolinů lze rozšířit tak, aby se staly řádky v „šíření“, typu neeuklidovského geometrie dopadu ve kterém jsou každé dva body topologické roviny spojeny jedinečnou přímkou (jako v euklidovské rovině), ale ve které nemusí platit další axiomy euklidovské geometrie.
Dalším typem neeuklidovské geometrie je hyperbolická rovina, auspořádání hyperbolických linií v této geometrii byly také studovány. Jakákoli konečná sada čar v euklidovské rovině má kombinatoricky ekvivalentní uspořádání v hyperbolické rovině (např. Uzavřením vrcholů uspořádání velkou kružnicí a interpretací vnitřku kružnice jako Klein model hyperbolické roviny). V uspořádání hyperbolických linií se však linky mohou vyhnout křížení navzájem, aniž by byly paralelní; the průsečíkový graf řádků v hyperbolickém uspořádání je a kruhový graf. Odpovídající koncept uspořádání hyperbolických linek pro pseudoliny je a slabé pseudolinové uspořádání,[35] skupina křivek se stejnými topologickými vlastnostmi jako přímky[36] tak, že jakékoli dvě křivky v rodině se buď setkají v jednom křížení, nebo nemají žádný průnik.
Viz také
- Konfigurace (geometrie), uspořádání řádků a sada bodů se všemi řádky obsahujícími stejný počet bodů a se všemi body, které patří ke stejnému počtu řádků.
- Uspořádání (prostorový oddíl), rozdělení roviny dané překrytými křivkami nebo prostoru vyšší dimenze překrytými povrchy, aniž by bylo nutné, aby byly křivky nebo povrchy ploché.
- K-set (geometrie), k-množiny jsou spojeny projektivní dualitou s k-úrovněmi v liniových uspořádáních.
- Matematický most, most v Cambridge v Anglii, jehož paprsky tvoří uspořádání tečných linií k jeho oblouku
Poznámky
- ^ Aby bylo uspořádání lokálně konečné, může být každá ohraničená podmnožina roviny překročena pouze konečně mnoha řádky.
- ^ Grünbaum (1972), strana 4.
- ^ Steiner (1826); Agarwal & Sharir (2000).
- ^ U buněk, ve kterých je vodorovný spodní okraj, vyberte nejspodnější vrchol jako pravý koncový bod spodního okraje.
- ^ A b Chazelle, Guibas & Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke & Seidel (1986).
- ^ A b Bern a kol. (1991).
- ^ Aronov, Matoušek a Sharir (1994).
- ^ Dey (1998); Tóth (2001). Problém ohraničení složitosti k-úrovně nejprve studoval Lovász (1971) a Erdős a kol. (1973).
- ^ Alon a Győri (1986).
- ^ Balogh a kol. (2004); viz také Matoušek (1991).
- ^ Canham (1969); Clarkson a kol. (1990).
- ^ Ajtai a kol. (1982); Leighton (1983).
- ^ Székely (1997).
- ^ Melchior (1940); Grünbaum (2009).
- ^ Grünbaum (1972); Grünbaum (2009).
- ^ Grünbaum (2009)
- ^ Crowe & McKee (1968); Dirac (1951); Kelly & Moser (1958); Grünbaum (1972), strana 18.
- ^ Eppstein, Falmagne a Ovchinnikov (2007).
- ^ Eppstein (2006).
- ^ Grünbaum (1972); Levi (1926); Roudneff (1988).
- ^ Füredi a Palásti (1984); Grünbaum (1972).
- ^ Purdy (1979); Purdy (1980); Strommer (1977).
- ^ Edelsbrunner & Guibas (1989).
- ^ Fortune & Milenkovic (1991); Greene & Yao (1986); Milenkovic (1989).
- ^ Aharoni a kol. (1999).
- ^ Agarwal a kol. (1998); Chan (1999); Cole, Sharir a Yap (1987); Edelsbrunner & Welzl (1986).
- ^ Agarwal (1990); Agarwal, Matoušek a Sharir (1998); Edelsbrunner, Guibas & Sharir (1990).
- ^ Cole a kol. (1989).
- ^ Erickson (1997).
- ^ Bose a kol. (1996).
- ^ Eppstein & Hart (1999).
- ^ Grünbaum (1972); Agarwal & Sharir (2002).
- ^ Tato definice pochází z Grünbaum (1972). Porovnání alternativních definic pseudolinů viz Eppstein, Falmagne a Ovchinnikov (2007).
- ^ Shor (1991); Schaefer (2010).
- ^ de Fraysseix a Ossona de Mendez (2003).
- ^ Zde alternativní definice z Shor (1991), že pseudolin je obraz čáry pod a homeomorfismus letadla, je vhodné.
Reference
- Agarwal, P. K. (1990), "Rozdělovací uspořádání řádků II: Aplikace", Diskrétní a výpočetní geometrie, 5 (1): 533–573, doi:10.1007 / BF02187809.
- Agarwal, P. K.; de Berg, M .; Matoušek, J.; Schwarzkopf, O. (1998), „Konstruování úrovní v uspořádáních a Voronoiho diagramech vyššího řádu“, SIAM Journal on Computing, 27 (3): 654–667, CiteSeerX 10.1.1.51.5064, doi:10.1137 / S0097539795281840.
- Agarwal, P. K.; Matoušek, J.; Sharir, M. (1998), „Výpočet mnoha tváří v uspořádání čar a segmentů“, SIAM Journal on Computing, 27 (2): 491–505, doi:10.1137 / S009753979426616X, hdl:1874/17088.
- Agarwal, P. K.; Sharir, M. (2000), „Uspořádání a jejich aplikace“ (PDF), v Sack, J.-R.; Urrutia, J. (eds.), Příručka výpočetní geometrie, Elsevier, str. 49–119.
- Agarwal, P. K.; Sharir, M. (2002), „Uspořádání pseudořádků: dualita, algoritmy a aplikace“, Proc. 13. ACM-SIAM Symposium on Discrete Algorithms (SODA '02) „San Francisco: Society for Industrial and Applied Mathematics, s. 800–809.
- Ageev, A. A. (1996), „Kruhový graf bez trojúhelníků s chromatickým číslem 5“, Diskrétní matematika, 152 (1–3): 295–298, doi:10.1016 / 0012-365X (95) 00349-2.
- Aharoni, Y .; Halperin, D .; Hanniel, I .; Har-Peled, S.; Linhart, C. (1999), „Konstrukce on-line zón v uspořádání linií v rovině“, v Vitter, Jeffrey S.; Zaroliagis, Christos D. (eds.), Algorithm Engineering: 3rd International Workshop, WAE'99, London, UK, July 19–21 July, 1999, Proceedings, Přednášky v informatice, 1668, Springer-Verlag, str.139–153, CiteSeerX 10.1.1.35.7681, doi:10.1007/3-540-48318-7_13, ISBN 978-3-540-66427-7.
- Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982), „Crossgraph-free subgraphs“, Teorie a praxe kombinatorikyMatematická studia v Severním Holandsku, 60, Severní Holandsko, s. 9–12, PAN 0806962.
- Alon, N.; Győri, E. (1986), „Počet malých poloprostorů konečné množiny bodů v rovině“, Journal of Combinatorial Theory, Series A, 41: 154–157, doi:10.1016/0097-3165(86)90122-6.
- Aronov, B.; Matoušek, J.; Sharir, M. (1994), „O součtu čtverců komplexů buněk v uspořádání nadroviny“, Journal of Combinatorial Theory, Series A, 65 (2): 311–321, doi:10.1016/0097-3165(94)90027-2
- Artés, J. C .; Grünbaum, B.; Llibre, J. (1998), „O počtu neměnných přímek pro polynomiální diferenciální systémy“ (PDF), Pacific Journal of Mathematics, 184 (2): 207–230, doi:10.2140 / pjm.1998.184.207.
- Balogh, J .; Regev, O .; Smyth, C .; Steiger, W .; Szegedy, M. (2004), „Dlouhé monotónní cesty v liniovém uspořádání“, Diskrétní a výpočetní geometrie, 32 (2): 167–176, doi:10.1007 / s00454-004-1119-1.
- Bern, M. W .; Eppstein, D.; Plassman, P.E .; Yao, F. F. (1991), "Horizon theorems for lines and polygons", in Goodman, J. E.; Pollack, R .; Steiger, W. (eds.), Diskrétní a výpočetní geometrie: Příspěvky ze zvláštního roku DIMACS, DIMACS Ser. Diskrétní matematika. and Theoretical Computer Science (6. vyd.), Amer. Matematika. Soc., S. 45–66, PAN 1143288.
- Bose, P.; Evans, W .; Kirkpatrick, D. G.; McAllister, M .; Snoeyink, J. (1996), „Přibližování nejkratších cest v uspořádání linek“, Proc. 8. kanadská konf. Výpočetní geometrie, s. 143–148.
- de Bruijn, N. G. (1981), „Algebraická teorie Penrosových neperiodických naklonění roviny“ (PDF), Indagationes Mathematicae, 43: 38–66.
- Canham, R. (1969), „Věta o uspořádání přímek v rovině“, Israel J. Math., 7 (4): 393–397, doi:10.1007 / BF02788872, S2CID 123541779.
- Chan, T. (1999), Poznámky k k-úrovňové algoritmy v rovině, archivovány z originál dne 04.11.2010.
- Chazelle, B.; Guibas, L. J.; Lee, D. T. (1985), „Síla geometrické duality“, BIT Numerická matematika, 25 (1): 76–90, doi:10.1007 / BF01934990, S2CID 122411548.
- Clarkson, K.; Edelsbrunner, H.; Guibas, L. J.; Sharir, M.; Welzl, E. (1990), „Hranice kombinatorické složitosti pro uspořádání křivek a koulí“, Diskrétní a výpočetní geometrie, 5 (1): 99–160, doi:10.1007 / BF02187783.
- Cole, Richard; Salowe, Jeffrey S .; Steiger, W. L .; Szemerédi, Endre (1989), „Algoritmus optimálního času pro výběr sklonu“, SIAM Journal on Computing, 18 (4): 792–810, doi:10.1137/0218055, PAN 1004799.
- Cole, R .; Sharir, M.; Yap, C.-K. (1987), „On k-trupy a související problémy ", SIAM Journal on Computing, 16 (1): 61–77, doi:10.1137/0216005.
- Crowe, D. W .; McKee, T. A. (1968), „Sylvesterův problém v kolineárních bodech“, Matematický časopis, 41 (1): 30–34, doi:10.2307/2687957, JSTOR 2687957.
- Dey, T. L. (1998), „Vylepšené hranice pro rovinné k-sady a související problémy ", Diskrétní a výpočetní geometrie, 19 (3): 373–382, doi:10.1007 / PL00009354, PAN 1608878.
- Dirac, G. (1951), "Vlastnosti kollinearity množin bodů", Quarterly Journal of Mathematics, 2 (1): 221–227, Bibcode:1951QJMat ... 2..221D, doi:10.1093 / qmath / 2.1.221.
- Edelsbrunner, H. (1987), Algoritmy v kombinatorické geometriiMonografie EATCS v teoretické informatice, Springer-Verlag, ISBN 978-3-540-13722-1.
- Edelsbrunner, H.; Guibas, L. J. (1989), „Topologically sweeping anorder“, Journal of Computer and System Sciences, 38 (1): 165–194, doi:10.1016 / 0022-0000 (89) 90038-X.
- Edelsbrunner, H.; Guibas, L. J.; Sharir, M. (1990), „Složitost a konstrukce mnoha tváří v uspořádání linií a segmentů“, Diskrétní a výpočetní geometrie, 5 (1): 161–196, doi:10.1007 / BF02187784.
- Edelsbrunner, H.; O'Rourke, J.; Seidel, R. (1986), "Konstrukční uspořádání linií a hyperplánů s aplikacemi", SIAM Journal on Computing, 15 (2): 341–363, doi:10.1137/0215024.
- Edelsbrunner, H.; Welzl, E. (1986), „Konstrukce pásů ve dvourozměrných uspořádáních s aplikacemi“, SIAM Journal on Computing, 15 (1): 271–284, doi:10.1137/0215019.
- Eppstein, D. (2006), „Krychlové dílčí kostky ze zjednodušeného uspořádání“, Electronic Journal of Combinatorics, 13 (1, R79): 1–14, arXiv:math.CO/0510263, doi:10.37236/1105, PAN 2255421, S2CID 8608953.
- Eppstein, D.; Falmagne, J.-Cl.; Ovchinnikov, S. (2007), Teorie médií, Springer-Verlag.
- Eppstein, D.; Hart, D. (1999), "Nejkratší cesty v uspořádání s k orientace čáry ", Sborník 10. sympozia ACM – SIAM o diskrétních algoritmech (SODA '99), str. 310–316.
- Erdős, P.; Lovász, L.; Simmons, A .; Straus, E. G. (1973), „Disekční grafy sad rovinných bodů“, Přehled kombinatorické teorie (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), Amsterdam: Severní Holandsko, s. 139–149, PAN 0363986.
- Erickson, J. (1997), Nejkratší cesty v uspořádání řádků, archivovány z originál dne 03.12.2008, vyvoláno 2008-12-15.
- Fortune, S .; Milenkovic, V. (1991), "Numerická stabilita algoritmů pro uspořádání řádků", Proc. 7. ACM Symposium on Computational Geometry (SoCG '91), str. 334–341, CiteSeerX 10.1.1.56.2404, doi:10.1145/109648.109685, ISBN 978-0897914260, S2CID 2861855.
- de Fraysseix, H .; Ossona de Mendez, P. (2003), „Stretching of Jordan arc contact systems“, Sborník z 11. mezinárodního sympozia o kreslení grafů (GD 2003), Lecture Notes in Computer Science (2912 ed.), Springer-Verlag, str. 71–85.
- Füredi, Z.; Palásti, I. (1984), "Uspořádání čar s velkým počtem trojúhelníků" (PDF), Proceedings of the American Mathematical Society, 92 (4): 561–566, doi:10.2307/2045427, JSTOR 2045427
- Greene, D .; Yao, F. F. (1986), „Výpočtová geometrie s konečným rozlišením“, Sborník 27. sympozia IEEE o základech informatiky (FOCS '86), str. 143–152, doi:10.1109 / SFCS.1986.19, ISBN 978-0-8186-0740-0, S2CID 2624319.
- Grünbaum, B. (1972), Uspořádání a spready, Regionální konferenční seriál z matematiky, 10„Providence, R.I .: American Mathematical Society.
- Grünbaum, Branko (2009), „Katalog zjednodušených uspořádání v reálné projektivní rovině“, Ars Mathematica Contemporanea, 2 (1): 1–25, doi:10.26493 / 1855-3974.88.e12, hdl:1773/2269, PAN 2485643.
- Kelly, L. M.; Moser, W. O. J. (1958), „O počtu obyčejných řádků určených n body ", Kanadský žurnál matematiky, 10: 210–219, doi:10.4153 / CJM-1958-024-6.
- Leighton, F. T. (1983), Problémy se složitostí ve VLSI„Foundations of Computing Series, Cambridge, MA: MIT Press.
- Levi, F. (1926), „Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade“, Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Lipsko, 78: 256–267.
- Lovász, L. (1971), „O počtu půlících čar“, Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica, 14: 107–108.
- Matoušek, J. (1991), „Dolní hranice délky monotónních cest v uspořádání“, Diskrétní a výpočetní geometrie, 6 (1): 129–134, doi:10.1007 / BF02574679.
- Melchior, E. (1940), „Über Vielseite der projektiven Ebene“, Deutsche Mathematik, 5: 461–475.
- Milenkovic, V. (1989), „Geometrie s dvojitou přesností: obecná technika pro výpočet průsečíků čar a segmentů pomocí zaoblené aritmetiky“, Sborník 30. konference IEEE o základech informatiky (FOCS '89), str. 500–505, doi:10.1109 / SFCS.1989.63525, ISBN 978-0-8186-1982-3, S2CID 18564700.
- Motzkin, Th. (1951), „Čáry a roviny spojující body konečné množiny“, Transakce Americké matematické společnosti, 70 (3): 451–464, doi:10.2307/1990609, JSTOR 1990609.
- Purdy, G. B. (1979), "Trojúhelníky v uspořádání čar", Diskrétní matematika, 25 (2): 157–163, doi:10.1016 / 0012-365X (79) 90018-9.
- Purdy, G. B. (1980), "Trojúhelníky v uspořádání linií, II", Proceedings of the American Mathematical Society, 79: 77–81, doi:10.1090 / S0002-9939-1980-0560588-4.
- Roudneff, J.-P. (1988), „Uspořádání čar s minimálním počtem trojúhelníků je jednoduché“, Diskrétní a výpočetní geometrie, 3 (1): 97–102, doi:10.1007 / BF02187900.
- Schaefer, Marcus (2010), „Složitost některých geometrických a topologických problémů“ (PDF), Grafická kresba, 17. mezinárodní sympozium, GS 2009, Chicago, IL, USA, září 2009, revidované práce, Přednášky v informatice, 5849, Springer-Verlag, str. 334–344, doi:10.1007/978-3-642-11805-0_32, ISBN 978-3-642-11804-3.
- Shor, P. W. (1991), „Roztažitelnost pseudolinů je NP-tvrdá“, Gritzmann, P .; Sturmfels, B. (eds.), Aplikovaná geometrie a diskrétní matematika: Victor Klee Festschrift Série DIMACS v diskrétní matematice a teoretické informatice, 4„Providence, R.I .: American Mathematical Society, s. 531–554.
- Steiner, J. (1826), „Einige Gesetze über die Theilung der Ebene und des Raumes“, J. Reine Angew. Matematika., 1: 349–364, doi:10,1515 / crll.1826.1.349, S2CID 120477563.
- Strommer, T. O. (1977), "Trojúhelníky v uspořádání čar", Journal of Combinatorial Theory, Series A, 23 (3): 314–320, doi:10.1016 / 0097-3165 (77) 90022-X.
- Székely, L. A. (1997), „Křížení čísel a těžké Erdőovy problémy v diskrétní geometrii“ (PDF), Kombinatorika, pravděpodobnost a výpočet, 6 (3): 353–358, doi:10.1017 / S0963548397002976.
- Tóth, G. (2001), „Bodové množiny s mnoha k-sady ", Diskrétní a výpočetní geometrie, 26 (2): 187–194, doi:10,1007 / s004540010022.