Geometric Structures on Points inside a Simple Polygon

Abstract

다각 공간에서 두 점 사이의 거리는 두 점을 연결하며 다각 공간의 내부에 포함된 가장 짧은 경로의 길이로 정의된다. 유클리드 공간에서 정의된 기하학적 구조들은 이 정의를 바탕으로 다각 공간으로 확장된다. 본 학위 논문에서는 보로노이 다이어그램 (Voronoi diagram) 과 컨벡스 헐 (Convex hull) 을 비롯한 기본적인 기하학적 구조를 다각 공간에서 계산하는 알고리즘을 제시했다.

첫째, 최근접점 보로노이 다이어그램과 (Nearest-point Voronoi diagram) 최장 보로노이 다이어그램 (Farthest-point Voronoi diagram)을 구하는 알고리즘의 개선된 수행시간을 제시했다. 다각 공간의 복잡도가 $m$ 이고 입력 점의 수가 $n$ 인 경우, 기존에 알려진 알고리즘은 $O(n\log n+m\log m)$ 의 수행 시간을 갖는다. 기존에 알려진 수행 시간의 하한은 $\Omega(n+m\log m)$ 이므로 두 보로노이 다이어그램을 구하는 최적 수행 시간에 대한 가장 잘 알려진 상한과 하한 사이에는 차이가 존재한다. 본 학위 논문에서는 기존 수행 시간보다 개선된 알고리즘을 제시함으로써 상한과 하한의 차이를 줄였다. 또한 제시된 알고리즘은 $m\leq n/\polylog n$ 인 경우 최적이며 기존 알고리즘은 $m\geq n$ 인 경우 최적이라는 점을 보였다. 따라서 $n/\polylog n< m < n$ 인 경우를 제외한 모든 구간에서 최적 수행 시간이 $\Theta(n+m\log m)$ 이라는 점을 증명했다.

둘째, 동적 다각 공간에서의 컨벡스 헐 (Convex hull) 을 유지하는 알고리즘과 위치 찾기 질의 (Point location query) 에 답하는 자료 구조를 제시했다. 기존 연구는 선분의 입력과 점의 삭제만을 허용하는 동적 다각 공간에 한하여 컨벡스 헐을 유지할 수 있었다. 본 학위 논문에서 제시된 알고리즘은 선분의 삭제와 점의 입력 모두를 허용하는 동적 다각 공간에서 컨벡스 헐을 유지하는 알고리즘을 구하는 최초의 결과이다. 동적 공간에서의 위치 찾기 질의 문제는 많이 연구 되었지만, 이들은 동적 공간이 연결된 경우에서만 동작한다. 일반적인 동적 공간에서 위치 찾기 질의를 허용하는 자료 구조를 찾는 문제는 오랜 시간 중요한 문제라고 언급 되었지만, 거의 연구가 되지 않았다. 본 학위 논문은 이에 대한 효율적인 자료 구조를 제시했다.

In this thesis, we consider a few fundamental geometric structures inside a simple polygon including Voronoi diagrams and convex hulls. Although the problems of computing several geometric structures in a simple polygon are well studied even as early as the 1980s, the optimal running times for computing Voronoi diagrams inside a simple polygon are not known. Also, the geometric structures in a simple polygon under dynamic settings have received less attention than the ones under the static setting.

The first part of the thesis considers the geodesic nearest-point and geodesic farthest-point Voronoi diagrams inside a simple polygon. For the nearest-point and the farthest-point Voronoi diagrams, algorithms for computing them inside a simple polygon are given by Papadopoulou and Lee and Aronov et al, respectively. However, there are gaps between these running times and the best known lower bounds. In this thesis, we reduce these gaps by presenting faster algorithms for computing the nearest-point and farthest-point Voronoi diagrams. This is the first improvement on these problems since the early 1990s.

The second part of the thesis considers geometric structures under dynamic settings. Previously, an algorithm for maintaining the geodesic convex hull was known only for a semi-dynamic setting. and it was open whether the geodesic convex hull can be maintained in the fully dynamic setting. We present the first nontrivial algorithm for maintaining the geodesic convex hull in the fully dynamic setting. Also, we consider the point location on dynamic general subdivisions which are not necessarily connected. Although there are several results on dynamic connected subdivisions, little is known for dynamic general subdivisions. Thus our result is the first nontrivial result on this problem.