Line and hyperplane centers of a point set

Abstract

The center problem is a classical problem in computational geometry, which can be applied to facility location, clustering, shape analysis, dimension reduction, etc. In this thesis, we focus on the variants of the hyperplane center problem. In particular, we first consider the problem of computing an optimal rearrangement a sequence of points in the plane onto a line. Given a sequence of n points ⟨p1, p2, . . . , pn⟩ in the plane, an optimal rearrangement of the points onto a line is ⟨q1, q2, . . . , qn⟩ such that each point of the rearrangement lies on the line and any two consecutive points qi and qi+1 are at distance no more than unit distance while the maximum distance between pi and qi over i is minimized. We present three efficient algorithms to compute an optimal rearrangement either under the L1 metric or the Euclidean metric. When the line is fully specified or partially specified by its orientation, our algorithms take near-linear time. When we have to choose a best target line over all lines in the plane, our algorithm takes O(n^3 log^4 n) time. Additionally, we consider the problem of computing parallel 2-hyperplane-center of given points in high dimension. We compute parallel 2-hyperplane-center by computing a pair of parallel slabs, called double-slab. We address two optimization problems in R^d for any fixed dimension d ≥ 3: the widest empty slab problem, in which one wants to maximize the gap between the two slabs, and the minimum-width doubleslab problem, in which one wants to minimize the maximum width of the two slabs.

점 집합의 중심 계산 알고리즘 개발은 계산기하학에 있어 기초적인 과제로, 시설 배치, 점 군집분석, 형태분석, 저차원 표현 등에 활용된다. 본 학위논문에서는 그 중에서 점 집합의 초평면 중심을 계산하는 알고리즘을 다룬다. 구체적으로, 우리는 먼저 점 순열에서 직선으로의 최적 재배치를 계산하는 알고리즘을 제시한다. 평면에 주어진 n개의 점 순열 ⟨p1, p2, . . . , pn⟩의 직선으로의 최적 재배치는 모든 점이 직선 위에 있으며 임의의 연속한 두 점 qi와 qi+1 사이의 거리가 단위 거리 이내가 되도록 하는 점 순열 ⟨q1, q2, . . . , qn⟩ 중 pi와 qi 사이 거리 중 최댓값을 최소화하도록 하는 순열이다. 우리는 L1 거리와 유클리드 거리 하에서 최적 재배치를 계산하는 세개의 효율적인 알고리즘을 제시한다. 재배치하고자하는 직선이 주어지거나, 직선의 기울기만 주어졌을 경우 우리의 알고리즘은 근-선형 시간을 소요한다. 임의의 직선 중 우리가 최적의 직선을 계산하는 경우는 우리 알고리즘은 O(n^3 log^4 n) 시간을 소요한다. 또한 우리는 고차원에 주어진 점에 대하여 평행한 초평면 2-중심 계산 알고리즘을 제시한다. 우리의 알고리즘은 이중 슬라브라고 불리는 평행한 한 쌍의 슬라브를 계산함으로서 초평면 2-중심을 구한다. 우리는 주어진 d ≥ 3에 대해 R d 공간의 점들에 대한 두 가지 문제에 대한 효율적인 알고리즘을 제시한다: 가장 넓은 슬라브 계산 문제는 이중 슬라브를 이루는 두 슬라브 사이 거리를 최대로 하는 이중 슬라브 를 계산하며, 가장 좁은 이중 슬라브 계산 문제는 두 슬라브 중 큰 폭을 최소화하는 이중 슬라브를 계산한다