마지막 Thiessen 다각형을 가지면 초기 점 집합을 찾을 수 있습니까?

Question

나는 보로 노이 알고리즘을 뒤집을 방법을 찾고있다.

기본적으로 대부분 삼각형과 사각형으로 구성된 연결된 모양을 가지고 있으며, 보로 노이 알고리즘을 사용하여 초기 모양을 다시 만드는 점 집합을 찾으려고합니다.

Answer 1

소개. 이 문제는 1985 년 Ash와 Boker가 부분 해답을 한 후 2013 년 Biedl et al.에 의해 해결되었습니다. Voronoi 노드가 모두 이상한 경우 Ash와 Bolker의 알고리즘이 효과적입니다. 점 설정되어 있지만 많은 포인트가되지 않을 수도있는 모든 노트의

먼저 모든 당신이 물어 같은 보로 노이 다이어그램을 가지고 설정합니다. 예를 들어, this website에서 찍은 사진

을 고려하십시오. 빨간색 포인트 세트와 파란색 포인트 세트는 동일한 검은 색 보로 노이 다이어그램을 제공합니다. (그런데, 적색과 청색의 다각형의 straight skeletons은 점 집합의 보로 노이 다이어그램과 일치합니다.)

알고리즘 개요. 대략적인 아이디어는 다음과 같습니다. 오라클이 Voronoi 셀에서 하나의 후보 지점을 말한 것으로 가정합니다. 그러면이 지점을 이웃하는 보로 노이 (Voronoi) 세포들과 이웃하는 세포들 사이의 공통 경계로 대칭시켜 계속 전파 할 수 있습니다.

그러나 문제가있을 수 있습니다. 미러링 된 지점이 인접 셀 외부에있을 수 있습니다. 또한 Voronoi 노드와 인시던트 셀을 고려해 보면 Voronoi 사건의 한주기 주변을 계속 전파 할 수는 있지만 다시 원래 지점으로 돌아 가지 않을 수도 있습니다.

• 그것은 보로 노이 다이어그램을 형성하기 위해 귀하의 의견에 대한 충분하고 필요한 조건을 제공합니다

  는 그래서 용지가하는 일은 다음과 같다.

• 유효한 시작점을 선택하는 방법을 알려줍니다. 사실, 모든 가능한 출발점 세트를 제공합니다.

다음과 같이 두 번째 부분은 거의 작동 : 각 보로 노이 셀 하나가 포인트가 셀의 보로 노이 노드를 조사하여 거짓말을 가지고있는 "지역을"알고있다. 그런 다음 보로 노이 다이어그램의 이중 그래프의 스패닝 트리를 가져 와서 임의의 루트를 선택하십시오. 모든 셀에 대해 "루트 셀"에 고유 한 "미러링 경로"가 있습니다. 위에서 언급 한 영역의 미러링 시퀀스를 적용하고 미러 이미지를 교차시킵니다.

교차점은 가능한 모든 시작점 집합입니다. 비어있는 경우 입력은 보로 노이 다이어그램이 아닙니다.

단순화. Voronoi 노드가 이상한 경우 문제가 훨씬 간단합니다.비들 (Biedl) 등의 논문에서 그림 4를 고려하십시오. 각 노드에 대해 포인트가 놓여 있어야하는 라인을 찾으십시오. Voronoi 셀에 홀수 차수의 노드가 2 개있는 경우이 선들과 교차하여 가능한 단일 후보 점을 얻을 수 있습니다. 모든 Voronoi 셀에 대해이 작업을 수행 할 수 있습니다.

Answer 2

모든 삼각형의 중심을 찾지 못하면 정의에 의한 점을 가능한 한 다른 점에서 얻을 수 있습니다.