평면성

Planarity는 웨스트 미시간 대학교의 Mary Radcliffe의 개념을 바탕으로 한 존 탄탈로의 퍼즐 컴퓨터 게임이다.^[1]이름은 그래프 이론의 평면 그래프의 개념에서 유래한다. 이것들은 가장자리가 교차하지 않도록 유클리드 평면에 삽입될 수 있는 그래프들이다.파리의 정리로는, 만약 그래프가 평면이라면, 교차 없이 그려질 수 있어, 그것의 모든 가장자리가 직선 세그먼트가 되도록 한다.평면 게임에서 플레이어는 모든 정점을 하나의 원에 배치하고 많은 교차점을 갖는 평면 그래프의 원형 레이아웃을 제공한다.플레이어의 목표는 모든 교차점을 제거하고 정점을 하나씩 더 나은 위치로 이동하여 그래프를 직선으로 내장하는 것이다.

기록 및 버전

이 게임은 케이스 웨스턴 리저브 대학의 존 탄탈로가 플래시로 썼다.^[2]온라인에서의 인기와 그가 얻은 지역적인 악명은 탄탈로를 2006년 클리블랜드에서 가장 흥미로운 사람들 중 한 명으로 선정했다.^[3][4]그것은 차례로 Xiph.org의 Chris Montgomery에 의해 GTK+ 버전을 만들도록 영감을 주었다. 이 회사는 추가 레벨 생성 알고리즘과 동시에 여러 노드를 조작할 수 있는 능력을 가지고 있다.^[5]

퍼즐 생성 알고리즘

평면 퍼즐의 정의는 퍼즐의 평면 그래프가 어떻게 생성되는가에 따라 달라지지 않지만, 원래 구현에서는 다음과 같은 알고리즘을 사용한다.

1. 평면에서 두 선이 평행하지 않고 한 점에서 세 선이 일치하지 않도록 일련의 랜덤 선을 생성한다.
2. 모든 선 쌍의 교차점을 계산한다.
3. 두 교차로(선들의 배열)를 연결하는 각 교차로에 대한 정점과 각 선 세그먼트에 대한 가장자리가 있는 그래프를 만드십시오.

If a graph is generated from ${\displaystyle L}$ lines, then the graph will have exactly ${\displaystyle {\tbinom {L}{2}}={\tfrac {L(L-1)}{2}}}$ vertices (each line has ${\displaystyle L-1}$ vertices, and each vertex is shared with one other line) and ${\displays$$Tyle L(L-2)}$개의$$ 모서리(각 선에는 ${\displaystyle \mathrm{L}}$- 2 ${\displaystyle L-2}$개의$$ 모서리 포함)Planarity의 첫 번째 $레벨$은 L${\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle L=4}$줄로$$ 구축되어 있어 $L{\displaystyle (\mathrm{L}}$- 1${\displaystyle }$)${\displaystyle }$/ ${\displaystyle 2}$= 6 ${\displaystyle$ L$(L-1)/2=6}$ 정점과$$ ${\displaystyle \mathrm{L}(L}$- ${\displaystyle 2}$)${\displaystyle }$= 8 ${\displaysty L(L-2)=8}$ 에지가$$ 있다.다음 각 레벨은 마지막 라인보다 한 라인 더 생성된다.레벨이 $L{\displaystyle }$ ${\displaystyle L}$ 라인으로$$ 생성된 경우 다음 레벨에는 $L{\displaystyle }$ ${\displaystyle L}$ 정점이 더 많고$$ 2 ${\displaystyle \mathrm{L}}$- 1 ${\displaystyle 2L-1}$에지가 더 많은 경우$$

선 배열의 그래프를 구성하기 위한 계산 기하학에서 가장 잘 알려진 알고리즘은 구성할 그래프 크기의 $선형$인 ^[6]O${\displaystyle }$( ${\displaystyle {L\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(L^{2})$ 시간 내에$$ 문제를 해결하지만 다소 복잡하다.대안으로 그리고 보다 간단하게 각 교차점을 그 지점에서 교차하는 선 쌍으로 색인화하고, $각{\displaystyle }$ 선에 따른 교차점을 x ${\$$displaystyle$ x$}$ - 좌표로$$ 정렬하고, 평면 그래프의 가장자리를 거의 $최적{\displaystyle }$ O$L2$ ${\displaystyle \log }$ ${\displaystyle }$ L${\displaystyle }$)로$생성$하기 위해 이 정렬된 순서를 사용할 수 있다$.$$L)}$시간$$.그래프의 꼭지점과 가장자리가 생성되면 임의 순열을 사용하여 원을 중심으로 균일하게 배치될 수 있다.

관련 이론 연구

그래프가 평면인지 아닌지를 판단하는 문제는 선형 시간 내에 해결할 수 있으며,^[7] 그러한 그래프는 파리의 정리에 의해 직선 내장될 수 있다고 보장되는데, 이는 선형 시간대의 평면 임베딩에서도 찾을 수 있다.^[8]그러므로 어떤 퍼즐도 컴퓨터가 선형적으로 해결할 수 있었다.하지만 이런 퍼즐은 인간 선수들이 풀기에는 그리 간단하지 않다.

계산 기하학 분야에서는, 가장자리 교차를 제거하기 위해 그래프에 내장된 정점의 부분집합을 이동하는 과정은 Pach와 Tardos(2002) 등이 연구해 왔으며,^[9] 평면성 퍼즐에서 영감을 얻었다.^{[10][11][12][13]}이러한 연구자들의 결과는 (이론적으로 놀이장이 경계 직사각형이 아닌 무한 평면이라고 가정) 단점을 위해 n ${\displaystyle n^{\$$epsilon }}}$은(는) 원래 위치에 고정된 채로 퍼즐을 푸는 것이 항상 가능하다는 것을 보여준다.정확히 결정되지는 않았지만 1/4에서 1/2 미만에 놓여 있는$$ 탠트 $ϵ{\displaystyle }$ ${\displaystyle \epsilon$}풀릴 평면 그래프가 주기 그래프인 경우 더 많은 수의 정점을 제자리에 고정할 수 있다.그러나 특정 입력 퍼즐(또는 동등하게 퍼즐을 푸는 데 필요한 최소 이동 수)을 위해 남겨둘 수 있는 가장 많은 정점 수를 결정하는 것은 NP-완전이다.

Verbitsky(2008)는 Planitarity의 초기 상태에 사용된 무작위화된 원형 레이아웃이 교차 수 측면에서 거의 최악이라는 것을 보여주었다. 즉, 어떤 평면 그래프가 엉킬 것인지에 관계없이, 이 레이아웃에 대한 교차 수의 예상 값은 교차 수 중 가장 많은 교차 수 중 세 개의 요인 내에 있다.모든 ^[14]배치도

2014년 수학자 데이비드 엡스타인은 퍼즐 생성 알고리즘의 세부 사항을 바탕으로 원래의 Planarity 게임에서 생성된 평면 그래프를 해결하는 효과적인 알고리즘을 제공하는 논문을 발표했다^[15].

참조

외부 링크

• Planarity.net — 원래의 플래시 게임
• NetLogo 시스템 - NetLogo 시스템에서 샘플 프로그램(게임)으로 포함
• Planarity — SVG 및 d3 JavaScript 라이브러리를 사용한 버전
• Multitouch Planarity — libavg를 사용하여 Python으로 작성된 멀티플레이어 및 멀티터치 지원 버전.