불확실성 점들의 2-중심 찾기

Abstract

중심 찾기 문제 (Euclidean center problem)는 시설 위치 문제 (Facility location problem)의 일종으로 다양한 응용 분야를 가지고 있는 실용적인 문제이며, 컴퓨 터과학 분야에서 중요하게 다뤄지고 있는 주제 중 하나이다. 본 학위 논문에서는 불확실성 점들의 중심 2개를 구하는 문제 (2-center problem)에 관하여 다루었다. 불확실성 (Impreciseness)은 물체의 실제 데이터와 측정 데이터간의 오차를 고려 하기 위하여 제시된 주제로, 기하계산학 분야에서 활발한 연구가 이루어지고 있는 주제이다. 본 학위 논문에서는 디스크와 볼록 다각형으로 정의되는 불확실성 점들 에 관한 문제를 다루었다. 본 학위 논문에서는 불확실성 점들이 각각 디스크 혹은 정점이 상수개인 볼록 다 각형으로 정의되는 경우 다양한 기준으로 모든 불확실성 점들을 포함할 수 있는 최적의(반지름이 최소인) 반지름이 같은 두 개의 디스크를 찾는 결정적 알고리즘과 확률적 알고리즘을 제시한다. 또한, 디스크 집합 혹은 볼록 다각형 집합에 대하여 모든 원소를 관통하는 두 개의 점을 찾는 문제에 대한 결정적 알고리즘을 제시한다. – 34

The 2-center problem is a special case of the k-center problem. The k-center problem is a fundamental topic in the field of computational geometry. In this thesis, we study the Euclidean 2-center problem for imprecise points which are modeled by disks or convex polygons. The Euclidean 2-center problem for a set of n imprecise points in the plane is to find the two smallest congruent disks such that every imprecise point is contained in one of the two congruent disks. We give deterministic algorithms and randomized algorithms for a few variations of the 2-center problem for imprecise points. Our algorithms are faster than previously best known results.