Rovinnost - Planarity

Rovinnost je logická počítačová hra John Tantalo, založený na konceptu Mary Radcliffe v Western Michigan University.^[1]Název pochází z konceptu rovinné grafy v teorii grafů; to jsou grafy, které lze vložit do souboru Euklidovské letadlo takže se neprotínají žádné hrany. Podle Fáryho věta, je-li graf rovinný, lze jej nakreslit bez křížení, takže všechny jeho hrany jsou úsečky. Ve hře rovinnosti se hráči zobrazí a kruhové rozložení rovinného grafu se všemi vrcholy umístěnými na jednom kruhu as mnoha kříženími. Cílem hráče je eliminovat všechny přechody a vytvořit lineární vložení grafu přesunutím vrcholů jeden po druhém do lepších pozic.

Historie a verze

Tato hra byla napsána Blikat John Tantalo v Case Western Reserve University.^[2] Online popularita a místní proslulost, kterou získal, umístil Tantala jako jednoho z nejzajímavějších lidí Clevelandu pro rok 2006.^[3]^[4] To zase inspirovalo vznik a GTK + verze od Xiph.org je Chris Montgomery, který má další algoritmy generování úrovní a schopnost manipulovat s více uzly najednou.^[5]

Algoritmus generování hádanek

Definice skládačky rovinnosti nezávisí na tom, jak jsou generovány rovinné grafy v skládačce, ale původní implementace používá následující algoritmus:

Vytvořte sadu náhodných čar v rovině tak, aby žádné dvě čáry nebyly rovnoběžné a žádné tři čáry se nesetkaly v jednom bodě.
Vypočítejte průsečíky každého páru čar.
Vytvořte graf s vrcholem pro každý průsečík a hranou pro každý úsečkový spoj spojující dva průsečíky ( dohoda řádků).

Pokud je graf generován z ${displaystyle L}$ řádky, pak bude mít graf přesně ${displaystyle {binom {L} {2}} = {frac {L (L-1)} {2}}}$ vrcholy (každý řádek má ${displaystyle L-1}$ vrcholy a každý vrchol je sdílen s jednou další přímkou) a ${displaystyle L (L-2)}$ hrany (každý řádek obsahuje ${displaystyle L-2}$ hrany). První úroveň Planarity je postavena na ${displaystyle L = 4}$ řádky, tak to má ${displaystyle L (L-1) / 2 = 6}$ vrcholy a ${displaystyle L (L-2) = 8}$ hrany. Každá úroveň po je generována o jeden řádek více než poslední. Pokud byla úroveň generována pomocí ${displaystyle L}$ řádky, pak má další úroveň ${displaystyle L}$ více vrcholů a ${displaystyle 2L-1}$ více hran.

Nejznámější algoritmy z výpočetní geometrie pro konstrukci grafů liniových uspořádání vyřeší problém v ${displaystyle O (L ^ {2})}$ čas,^[6] lineární ve velikosti vytvořeného grafu, ale jsou poněkud složité. Alternativně a jednodušeji je možné indexovat každý bod křížení dvojicí linií, které se v tomto bodě protínají, třídit přechody podél každé linie podle jejich ${displaystyle x}$ -coordinates a použijte toto seřazené uspořádání ke generování okrajů rovinného grafu v téměř optimálním stavu ${displaystyle O (L ^ {2} log L)}$ čas. Jakmile jsou vrcholy a hrany grafu vygenerovány, mohou být pomocí a umístěny rovnoměrně kolem kruhu náhodná obměna.

Související teoretický výzkum

Problém určení, zda je graf rovinný lze vyřešit v lineární čas,^[7] a je zaručeno, že každý takový graf bude mít lineární vložení Fáryho věta, které lze také zjistit z rovinného uložení v lineárním čase.^[8] Proto by každá hádanka mohla být vyřešena v lineárním čase počítačem. Tyto hádanky však nejsou tak jednoduché, aby je lidští hráči mohli vyřešit.

V oblasti výpočetní geometrie, proces přesunu podmnožiny vrcholů do grafu vloženého k eliminaci křížení hran studovali Pach a Tardos (2002),^[9] a další, inspirovaní hádankou rovinnosti.^[10]^[11]^[12]^[13] Výsledky těchto vědců ukazují, že (teoreticky, za předpokladu, že hracím polem je spíše nekonečná rovina než ohraničený obdélník), je vždy možné vyřešit hádanku při opuštění ${displaystyle n ^ {epsilon}}$ z ${displaystyle n}$ vstupní vrcholy fixované na místě v jejich původních polohách, pro konstantu ${displaystyle epsilon}$ to nebylo přesně určeno, ale leží mezi 1/4 a o něco méně než 1/2. Když je rovinný graf, který má být rozmotán, a graf cyklu, může být na místě upevněn větší počet vrcholů. Určení největšího počtu vrcholů, které lze ponechat na místě pro konkrétní vstupní hádanku (nebo ekvivalentně nejmenší počet tahů potřebných k vyřešení hádanky), je NP-kompletní.

Verbitsky (2008) ukázal, že randomizované kruhové rozložení použitý pro počáteční stav Planarity je téměř nejhorší možný z hlediska jeho počet přechodů: bez ohledu na to, jaký rovinný graf má být zamotán, očekávaná hodnota počtu přechodů pro toto rozvržení je v rámci faktoru tři největšího počtu přejezdů ze všech rozvržení.^[14]

V roce 2014 matematik David Eppstein zveřejnil příspěvek^[15] poskytnutí účinného algoritmu pro řešení rovinných grafů vygenerovaných původní hrou Planarity na základě specifik algoritmu generování skládaček.

Reference

^ Arar, Yardena (1. srpna 2005), „Kočičí kolébka na steroidech“, Today @ PC World, PCWorld, archivovány z originál dne 4. 6. 2009
^ Massie, Laura (2005-06-20). „Případový student vyvíjí vzkvétající online hru“. Case Western Reserve University News Center. Citováno 2007-09-30.
^ Castro, Laura (18. 11. 2005). „Případový student je jedním z nejzajímavějších lidí v Clevelandu"". Pozorovatel. Archivovány od originál 8. září 2006. Citováno 2007-09-30.
^ „Nejzajímavější lidé 2006“ (Tisková zpráva). Clevelandský časopis. Leden 2006. Citováno 2015-05-19.
^ „gPlanarity home“.
^ Chazelle, B.; Guibas, L. J.; Lee, D. T. (1985), „Síla geometrické duality“, BIT, 25 (1): 76–90, doi:10.1007 / BF01934990
^ Mehlhorn, K.; Mutzel, P. (1996), „O fázi vkládání algoritmu testování rovinnosti Hopcroft a Tarjan“, Algorithmica, 16 (2): 233–242, doi:10,1007 / s004539900046, hdl:11858 / 00-001M-0000-0014-B51D-B, PAN 1394503
^ de Fraysseix, Hubert; Pach, János; Pollack, Richard (1990), „Jak nakreslit rovinný graf na mřížce“, Combinatorica, 10: 41–51, doi:10.1007 / BF02122694, PAN 1075065
^ Pach, János; Tardos, Gábor (2002), „Rozmotání mnohoúhelníku“, Diskrétní a výpočetní geometrie, 28 (4): 585–592, doi:10.1007 / s00454-002-2889-r
^ Bose, Prosenjit; Dujmovic, Vida; Hurtado, Ferran; Langerman, Stefan; Morin, Pat; Wood, David R. (2008), „Polynom vázaný na rozmotání geometrických rovinných grafů“, Diskrétní a výpočetní geometrie, 42 (4): 570–585, arXiv:0710.1641, doi:10.1007 / s00454-008-9125-3
^ Cibulka, Josef (2009), „Unangling Polygons and Graphs“, Diskrétní a výpočetní geometrie, 43 (2): 402–411, arXiv:0802.1312, doi:10.1007 / s00454-009-9150-x
^ Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander (2009), „Rozmotání rovinného grafu“, Diskrétní a výpočetní geometrie, 42 (4): 542–569, arXiv:0709.0170, doi:10.1007 / s00454-008-9130-6
^ Cano, Javier; Tóth, Csaba D .; Urrutia, Jorge (2014), „Horní vázané konstrukce pro rozmotání rovinných geometrických grafů“, SIAM Journal on Discrete Mathematics, 28 (4): 1935–1943, doi:10.1137/130924172, PAN 3277216
^ Verbitsky, Oleg (2008), „O obfuskační složitosti planárních grafů“, Teoretická informatika, 396 (1–3): 294–300, arXiv:0705.3748, doi:10.1016 / j.tcs.2008.02.032, PAN 2412266
^ Eppstein, David (2014), „Kreslení grafů uspořádání v malých mřížkách nebo jak hrát rovinnost“, Journal of Graph Algorithms and Applications, 18 (2): 211–231, arXiv:1308.0066, doi:10,7155 / jgaa.00319, PAN 3213195

externí odkazy

Planarity.net - původní Flash hra
Systém NetLogo - Zahrnuto jako ukázkový program (hra) v systému NetLogo
Rovinnost - Verze se používá SVG a d3 JavaScript knihovna
Multitouch Planarity - Verze pro více hráčů a více dotyků napsaná v Krajta pomocí libavg.

[1] Arar, Yardena (1. srpna 2005), „Kočičí kolébka na steroidech“, Today @ PC World, PCWorld, archivovány z originál dne 4. 6. 2009

[Case_news-2] Massie, Laura (2005-06-20). „Případový student vyvíjí vzkvétající online hru“. Case Western Reserve University News Center. Citováno 2007-09-30.

[Observer-3] Castro, Laura (18. 11. 2005). „Případový student je jedním z nejzajímavějších lidí v Clevelandu"". Pozorovatel. Archivovány od originál 8. září 2006. Citováno 2007-09-30.

[Cleveland_Magazine-4] „Nejzajímavější lidé 2006“ (Tisková zpráva). Clevelandský časopis. Leden 2006. Citováno 2015-05-19.

[5] „gPlanarity home“.

[6] Chazelle, B.; Guibas, L. J.; Lee, D. T. (1985), „Síla geometrické duality“, BIT, 25 (1): 76–90, doi:10.1007 / BF01934990

[7] Mehlhorn, K.; Mutzel, P. (1996), „O fázi vkládání algoritmu testování rovinnosti Hopcroft a Tarjan“, Algorithmica, 16 (2): 233–242, doi:10,1007 / s004539900046, hdl:11858 / 00-001M-0000-0014-B51D-B, PAN 1394503

[8] Fraysseix, Hubert; Pach, János; Pollack, Richard (1990), „Jak nakreslit rovinný graf na mřížce“, Combinatorica, 10: 41–51, doi:10.1007 / BF02122694, PAN 1075065

[9] Pach, János; Tardos, Gábor (2002), „Rozmotání mnohoúhelníku“, Diskrétní a výpočetní geometrie, 28 (4): 585–592, doi:10.1007 / s00454-002-2889-r

[10] Bose, Prosenjit; Dujmovic, Vida; Hurtado, Ferran; Langerman, Stefan; Morin, Pat; Wood, David R. (2008), „Polynom vázaný na rozmotání geometrických rovinných grafů“, Diskrétní a výpočetní geometrie, 42 (4): 570–585, arXiv:0710.1641, doi:10.1007 / s00454-008-9125-3

[11] Cibulka, Josef (2009), „Unangling Polygons and Graphs“, Diskrétní a výpočetní geometrie, 43 (2): 402–411, arXiv:0802.1312, doi:10.1007 / s00454-009-9150-x

[12] Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander (2009), „Rozmotání rovinného grafu“, Diskrétní a výpočetní geometrie, 42 (4): 542–569, arXiv:0709.0170, doi:10.1007 / s00454-008-9130-6

[13] Cano, Javier; Tóth, Csaba D .; Urrutia, Jorge (2014), „Horní vázané konstrukce pro rozmotání rovinných geometrických grafů“, SIAM Journal on Discrete Mathematics, 28 (4): 1935–1943, doi:10.1137/130924172, PAN 3277216

[14] Verbitsky, Oleg (2008), „O obfuskační složitosti planárních grafů“, Teoretická informatika, 396 (1–3): 294–300, arXiv:0705.3748, doi:10.1016 / j.tcs.2008.02.032, PAN 2412266

[15] Eppstein, David (2014), „Kreslení grafů uspořádání v malých mřížkách nebo jak hrát rovinnost“, Journal of Graph Algorithms and Applications, 18 (2): 211–231, arXiv:1308.0066, doi:10,7155 / jgaa.00319, PAN 3213195

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]