Delaunay triangulation is one of the most fundamental and well-studied topics in computational geometry. In particular, algorithms for constructing the Delaunay triangulation of moving points have also been proposed. However no previous work dealt with the Delaunay triangulation of moving points in distributed manner.
This thesis proposes a distributed algorithm to maintain the Delaunay triangulation of moving points. We assume that every point is a processor which can only communicate with the adjacent points connected by edges in the Delaunay triangulation. The topological changes of the Delaunay triangulation due to the movement of the points are updated automatically by local operations of the points without any centralized processor or global information. In addition, we present an efficient method that balances the maintenance load for each point. Our algorithm can be applied to construct a scalable network.
Delaunay 삼각형 분할은 계산기하학 분야에서 핵심적인 연구 주제 중 하나이다. 움직이는 노드들의 Delaunay 삼각형 분할을 구하는 문제 또한 널리 연구되어 왔다. 그러나 아직까지 움직이는 노드의 Delaunay 삼각형 분할을 분산 환경에서 유지하는 문제는 다루어 지지 않았다.
본 학위 논문에서는 움직이는 노드의 Delaunay 삼각형 분할을 유지, 관리하는 분산 알고리즘을 제안한다.각각의 노드는 간선으로 연결된 다른노드와 통신할 수 있는 프로세서라고 가정한다. 제안된 알고리즘은 노드들의 움직임에 따른 Delauany 삼각형 분할의 토폴로지 변화를 어떠한 중앙처리장치나 대역적 정보를 사용하지 않고 간선과 연결된 인접 노드들과의 정보 교환을 통해서 자동적으로 갱신한다. 또한, Delaunay triangulation의 topology를 유지하기 위한 각 노드의 work load를 효율적으로 분배하는 방법도 제안한다. .
