점집합을 포하하는 커버링 문제들

Abstract

In this thesis we consider following two problems. Given a set S of n points in the plane, the disjoint two rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In this problem we consider two variants of this optimization problem: (1) the rectangles are allowed to be reoriented freely while restricting them to be parallel to each other, and (2) one rectangle is restricted to be axis-parallel but the other rectangle is allowed to be reoriented freely. For both of the problems, we present O(n^2logn)-time algorithms using O(n) space. For a set of n points in the plane, we consider the axis aligned (p,k)-BOX COVERING problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this problem, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For a small, fixed number p, we give algorithms that find the solution in the following running times: For squares we have O(n+klogk) time for p = 1, and O(nlogn+k^plog^pk) time for p = 2, 3. For rectangles we get O(n+k^3) for p = 1 and O(nlogn + k^{2+p}log^{p-1}k) time for p = 2, 3. In all cases, our algorithms use O(n) space.

이 학위논문에서는 다음과 같은 두 개의 문제를 다룬다. n개의 점집합 S가 주어지면 disjoint two-rectangle covering문제는 S를 포함하면서 큰 직사각형의 크기가 최소가 되는 두 개의 직사각형을 찾는 문제이다. 이 문제에서 두 가지 종류의 최적화 문제를 다룬다 : (1) 두 직사각형이 서로 평행하지만 임의의 방향을 가지는 문제와 (2) 한 직사각형은 축에 평행하지만 다른 직사각형은 임의의 방향을 가지는 문제를 다룬다. 두 문제에 대해서 우리는 O(n2logn) 시간과 O(n)공간이 필요한 알고리즘을 제시한다. 평면에 있는 n개의 점에 대해 우리는 축에 평행한 (p,k)-BOXCOVREING문제를 다룬다: n-k개의 점을 포함하는 축에 평행하며 서로 평행한 p개의 상자를 구한다. 이 문제에서 상자는 정사각형이거나 직사각형이고, 우리는 큰상자의 크기를 최소화 한다. 고정된 작은 p에 대해 우리는 다음과 같은 시간이 걸리는 알고리즘을 제시한다: 정사각형의 경우, p = 1일 경우 O(n+klogk) 시간이 p = 2, 3일 경우 O(nlogn+k^plog^pk) 시간을 사용한다. 직사각형의 경우 p = 1일 경우 O(n+k^3) 시간이 p = 2, 3일 경우 O(nlogn + k^{2+p}log^{p-1}k) 시간을 사용한다. 모든 경우에 대해서 우리의 알고리즘은 O(n) 공간을 사용한다.