Planhet

Den här artikeln handlar om spelet. För egenskapen graph theory, se Planar graph .

Planarity är ett pussel datorspel av John Tantalo, baserat på ett koncept av Mary Radcliffe vid Western Michigan University . Namnet kommer från begreppet plana grafer i grafteorin; det här är grafer som kan bäddas in i det euklidiska planet så att inga kanter skär varandra. Enligt Fárys sats , om en graf är plan, kan den ritas utan korsningar så att alla dess kanter är raka linjesegment. I planaritetsspelet presenteras spelaren för en cirkulär layout av en plan graf, med alla hörn placerade på en enda cirkel och med många korsningar. Målet för spelaren är att eliminera alla korsningar och konstruera en rätlinjig inbäddning av grafen genom att flytta hörnen en efter en till bättre positioner.

Historik och versioner

Spelet skrevs i Flash av John Tantalo vid Case Western Reserve University . Online popularitet och den lokala ryktbarhet han fick placerade Tantalo som en av Clevelands mest intressanta personer för 2006. Det har i sin tur inspirerat skapandet av en GTK+ -version av Xiph.org:s Chris Montgomery , som har ytterligare nivågenereringsalgoritmer och förmågan att manipulera flera noder samtidigt.

Pusselgenereringsalgoritm

Definitionen av planaritetspusslet beror inte på hur de plana graferna i pusslet genereras, men den ursprungliga implementeringen använder följande algoritm:

1. Generera en uppsättning slumpmässiga linjer i ett plan så att inga två linjer är parallella och inga tre linjer möts i en enda punkt.
2. Beräkna skärningspunkterna för varje linjepar.
3. Skapa en graf med ett hörn för varje skärningspunkt och en kant för varje linjesegment som förbinder två skärningspunkter ( linjernas arrangemang ).

Om en graf genereras från $L$ -linjer, kommer grafen att ha exakt ${\tbinom {L}{2}}={\tfrac { L(L-1)}{2}}$ hörn (varje linje har $L-1$ hörn, och varje vertex delas med en annan linje) och $L (L-2)$ kanter (varje rad innehåller $L-2$ kanter). Den första planaritetsnivån är byggd med $L=4$ linjer, så den har $L(L-1)/2=6$ hörn och $L(L-2)=8$ kanter. Varje nivå efter genereras av en rad mer än den förra. Om en nivå genererades med $L$ -linjer, så har nästa nivå $L$ fler hörn och $2L-1$ fler kanter.

De mest kända algoritmerna från beräkningsgeometrin för att konstruera graferna för linjearrangemang löser problemet i $O(L^{2})$ tid, linjär i storleken på den graf som ska konstrueras, men de är något komplexa. Alternativt och enklare är det möjligt att indexera varje korsningspunkt efter paret av linjer som korsar vid den punkten, sortera korsningarna längs varje linje efter deras x {\displaystyle x} -koordinater $använda$ denna sorterade ordning för att generera kanterna av den plana grafen, i nästan optimal ${\displaystyle O(L^{2}\log L)}-$ tid. När grafens hörn och kanter har genererats kan de placeras jämnt runt en cirkel med en slumpmässig permutation .

Relaterad teoretisk forskning

Problemet med att avgöra om en graf är plan kan lösas i linjär tid , och varje sådan graf garanteras ha en rätlinjig inbäddning av Fárys teorem , som också kan hittas från den plana inbäddningen i linjär tid. Därför kan alla pussel lösas i linjär tid av en dator. Dessa pussel är dock inte lika enkla för mänskliga spelare att lösa.

Inom området för beräkningsgeometri har processen att flytta en delmängd av hörn i en grafinbäddning för att eliminera kantkorsningar studerats av Pach och Tardos (2002) och andra, inspirerade av planaritetspusslet. Resultaten från dessa forskare visar att (i teorin, om man antar att spelfältet är det oändliga planet snarare än en avgränsad rektangel) är det alltid möjligt att lösa pusslet samtidigt som man lämnar n ϵ {\displaystyle n^{\ $}$ av de $n$ ingångshörnen fixerade på sina ursprungliga positioner, för en konstant $\epsilon$ som inte har bestämts exakt men ligger mellan 1/4 och något mindre än 1/2. När den plana grafen som ska lossas är en cykelgraf , kan ett större antal hörn fixeras på plats. Fastställandet av det största antalet hörn som kan lämnas kvar för ett visst inmatningspussel (eller motsvarande det minsta antalet drag som behövs för att lösa pusslet) är NP-komplett .

Verbitsky (2008) har visat att den randomiserade cirkulära layouten som används för det initiala planaritetstillståndet är nästan den sämsta möjliga när det gäller antalet korsningar : oavsett vilken plan graf som ska trasslas, förväntas värdet av antalet korsningar för denna layout ligger inom en faktor tre av det största antalet korsningar bland alla layouter.

2014 publicerade matematikern David Eppstein en artikel som tillhandahåller en effektiv algoritm för att lösa plana grafer genererade av det ursprungliga Planarity-spelet, baserat på detaljerna i pusselgenereringsalgoritmen.

externa länkar

• Planarity.net — det ursprungliga Flash-spelet
• NetLogo System — Ingår som exempelprogram (spel) i NetLogo-systemet
• Planaritet — Version som använder SVG och d3 JavaScript -biblioteket
• Multitouch Planarity — Multiplayer- och multitouch-aktiverad version skriven i Python med libavg.