스트리밍 점들과 불확실성 점들의 유클리디언 센터들

Abstract

시설들의 위치를 찾는 문제는 컴퓨터 과학 분야의 많은 응용분야에서 중요한 질문중에 하나이다. 196대부터 오퍼레이션 리서치와 메니지먼트 분야에서 다양한 종류의 시설 입지 문제들이 (Facility Location Problems) 연구되어 왔다. 그리고 계산기하 분야의 발전으로 인해, 유클리디언 공간상의 문제들에 대해서 기하 속성들을 이용한 연구들이 진행되고 있다.

지난 십년간 수집되어지고 다양한 어플리케이션에서 사용되어지는 데이터의 양이 크게 증가하고 있다. 데이터의 증가하는 문제를 극복하기 위해서, 데이터를 유사성을 가지는 그룹으로 나누는 효율적인 알고리즘의 개발이 요구되어 진다.

유클리디언 k-센터 문제는 d차원 공간에 n개의 점들이 주어지면 k개의 가장 작은 구들을 구하는 문제로써 모든 입력점들이 구들의 합집합에 포함되어야 한다. 이 문제는 퍼실리티 로케이션 문제의 한 종류이며 클러스터링을 위해서도 사용되어 질 수 있다. 본 학위 논문에서는 유클리디안 k-센터 문제에 대해서 연구하고 이를 해결하기 위해서 효율적인 알고리즘들을 제시한다. 우리는 두가지 종류의 데이터에 대해서 다룬다: 하나는 스트리밍 점들에 대해서 다룬다. 그리고 다른 하나는 불확실성 점들에 대해서 다룬다. 우리는 이 데이터들에 대한 효율적인 알고리즘을 제시한다.

Finding locations of facilities is a fundamental question in many applications of computer science. Various variants of the facility location problem have been widely studied in the operations research and management science since the 1960s, and the development of computational geometry has inspired the development of geometric variants that use geometric properties to solve the problem. The amount of data collected and used by various applications has significantly increased over the last decades. To cope with this steadily increasing amount of data, an algorithm should be designed that efficiently clusters all data into groups of high relevance. Given n points in Rd, the Euclidean k-center problem asks to find the k smallest congruent balls whose union covers all the input points. This problem is a variant of the facility location problem and can be applied for clustering. In this thesis we study the Euclidean k-center problems. We consider two kinds of data set: one is streaming points and the other is imprecise points. We present efficient algorithms for those data set.