平面性

プラナリティは、ウェスタンミシガン大学のメアリー・ラドクリフのコンセプトに基づいて、ジョン・タンタロが2005年に開発したパズルコンピュータゲームです。^{[1]名前はグラフ理論の}平面グラフ の概念に由来しています。平面グラフとは、辺が交差しないようにユークリッド平面に埋め込むことができるグラフです。ファリの定理により、グラフが平面であれば、交差することなく、すべての辺が直線分になるように描くことができます。プラナリティゲームでは、プレーヤーには平面グラフの円形レイアウトが提示され、すべての頂点が単一の円上に配置され、多くの交差点があります。プレーヤーの目標は、すべての交差点をなくし、頂点を1つずつより良い位置に移動させることでグラフの直線埋め込みを構築することです。

このゲームは2005年にケース・ウェスタン・リザーブ大学のジョン・タンタロによってFlashで書かれました。^[2] オンラインでの人気と地元での知名度により、タンタロは2006年のクリーブランドで最も興味深い人物の一人となりました。^{[3] [4]このゲームは、} Xiph.orgのクリス・モンゴメリーによるGTK+バージョン の作成に影響を与え、追加のレベル生成アルゴリズムと複数のノードを同時に操作する機能を備えています。^[5]

平面性パズルの定義は、パズル内の平面グラフがどのように生成されるかには依存しませんが、元の実装では次のアルゴリズムが使用されます。

1. 2 本の線が平行にならず、3 本の線が 1 点で交わらないように、平面上にランダムな線のセットを生成します。
2. すべての直線ペアの交点を計算します。
3. 各交差点に頂点、2 つの交差点を結ぶ各線分に辺を持つグラフを作成します (線の配置)。

グラフが線から生成される場合、グラフには頂点 (各線には頂点があり、各頂点は他の 1 本の線と共有されます) とエッジ (各線にはエッジが含まれます) が正確に存在します。Planarity の最初のレベルは線で構築されるため、頂点とエッジが存在します。その後の各レベルは、前のレベルよりも 1 本多い線で生成されます。レベルが線で生成された場合、次のレベルにはより多くの頂点とエッジが存在します。 ${\displaystyle L}$${\displaystyle {\tbinom {L}{2}}={\tfrac {L(L-1)}{2}}}$${\displaystyle L-1}$${\displaystyle L(L-2)}$${\displaystyle L-2}$${\displaystyle L=4}$${\displaystyle L(L-1)/2=6}$${\displaystyle L(L-2)=8}$${\displaystyle L}$${\displaystyle L}$${\displaystyle 2L-1}$

計算幾何学における線分配置のグラフ構築のための最もよく知られたアルゴリズムは、構築するグラフのサイズに比例して時間的に問題を解決しますが、^[6]やや複雑です。あるいは、より単純に、各交差点をその点で交差する線のペアでインデックスし、各線に沿った交差点を -座標でソートし、このソートされた順序を使用して平面グラフのエッジをほぼ最適な時間で生成することもできます。グラフの頂点とエッジが生成されると、ランダムな順列を使用して円の周りに均等に配置できます。 ${\displaystyle O(L^{2})}$${\displaystyle x}$${\displaystyle O(L^{2}\log L)}$

グラフが平面であるかどうかを判断する問題は線形時間で解決できます。^{[7]また、そのようなグラフは}ファリーの定理によって直線埋め込みを持つことが保証されており、これも線形時間での平面埋め込みから見つけることができます。^[8]したがって、コンピューターはどのようなパズルでも線形時間で解くことができます。ただし、これらのパズルは人間のプレイヤーにとってそれほど簡単ではありません。

計算幾何学の分野では、グラフ埋め込みの頂点のサブセットを移動してエッジの交差をなくすプロセスが、平面性パズル^{[10] [11] [12] [13]にヒントを得て、Pach と Tardos (2002) [9]}らによって研究されてきた。これらの研究者の結果によると、(理論的には、競技場が境界のある長方形ではなく無限平面であると仮定すると)入力頂点を元の位置に固定したままパズルを解くことが常に可能であり、その定数は正確には決まっていないが、1/4 から 1/2 よりわずかに小さい値の間となる。解くべき平面グラフがサイクルグラフである場合、より多くの頂点を固定することができる。しかし、特定の入力パズルに対して残すことができる頂点の最大数 (またはパズルを解くために必要な最小の移動数) を決定することはNP 完全である。 ${\displaystyle n^{\epsilon}}$${\displaystyle n}$${\displaystyle \epsilon }$

Verbitsky (2008)は、平面性の初期状態に使用されるランダム化された円形レイアウトは、交差数の点でほぼ最悪のものであることを示しました。どの平面グラフを絡ませるかに関係なく、このレイアウトの交差数の期待値は、すべてのレイアウトの中で最大の交差数の3倍以内です。^[14]

2014年に数学者のデイビッド・エップスタインは、パズル生成アルゴリズムの詳細に基づいて、オリジナルのPlanarityゲームによって生成された平面グラフを解くための効果的なアルゴリズムを提供する論文^[15]を発表しました。

• Planarity.net — オリジナルの Flash ゲーム
• NetLogo システム — NetLogo システムにサンプルプログラム (ゲーム) として含まれています
• Planarity — SVGと d3 JavaScriptライブラリを使用したバージョン
• Multitouch Planarity — libavg を使用してPythonで記述された、マルチプレイヤーおよびマルチタッチ対応バージョン。