In this thesis, we study geometric permutations of a family F of n pairwise non-overlapping unit balls in $\R^d$. A line transversal to F is a line intersecting every member of F. The two linear orders on F induced by a line transversal can be described by two permutations that are the reverse of each other, so the two linear orders are equivalent. The equivalent classes are called geometric permutations of F, and a geometric permutation will be represented by any one of its two linear orders, for convenience.
In 2005, it was proved that there are at most two geometric permutations if $n \geq 9$, and at most three if $3 \leq n \leq 8$, by Cheong, Goaoc and Na [8]. In this thesis, we present a simple proof for the upper bounds, and provide all possibilities for a set of realizable geometric permutations. We also prove that there are at most two geometric permutations for n=7,8.
The main idea of our proof is the Distance Lemma which gives relations of the distances between centers of unit balls admitting a line transversal. This lemma provides the triple {ABCD, ACBD, ACDB} which contains all possibilities for a set of realizable geometric permutations for four unit balls.
The triple implies that if (ABCD, ACDB) is incompatible, then there are at most two geometric permutations for $n \geq 4$. We characterize a double pinning configuration relative to this pair, and minimal four-pinning configurations.
서로 겹치지 않는 유한개의 d차원 단위 공들의 집합 F가 있다고 하자. 만약 어떤 직선이 F에 속하는 모든 단위 공들을 지나면, 그 직선은 F의 횡단선이라고 불린다. 이 횡단선은 F의 원소를 통과하는 순서에 따라, F에 순열을 주게 된다. 하나의 직선은 두 개의 방향을 갖고 있으므로, F는 하나의 횡단선으로부터 두 개의 순열을 얻는다. 이러한 두 개의 순열은 동치관계에 있다. 이러한 동치류들을 F의 기하학적 순열들이라고 한다.
만약 F가 9개 이상의 단위 공들을 갖고 있으면, F의 기하학적 순열은 최대 2개, 만약 3개 이상 8개 이하의 단위 공들이 있으면 그 집합의 기하학적 순열은 최대 3개 있다는 것이, 2005년도에 밝혀졌다. 본 학위 논문에서는 이 두 개의 상한에 대한 새로운 간단한 증명방법을 제시하고, 7개 혹은 8개의 단위 공들의 집합에 대한 기하학적 순열이 최대 2개 있다는 것을 증명하였다.
그 두 개의 상한에 대한 증명은 거리 정리로부터 얻을 수 있다. 거리 정리는 주어진 순열의 횡단선이 있을 때, 공들의 중심들 사이의 거리들의 대소 관계를 알려준다. 이 정리로부터 네 개의 단위 공들이 가질 수 있는 기하학적 순열은 최대 3개이며, 이 순열들은 {ABCD, ACBD, ACDB}의 부분 집합으로 나타내어질 수 있음을 알 수 있다.
위의 사실은, 만약 ABCD와 ACDB를 동시에 기하학적 순열로 갖는 4개의 단위 공들이 존재하지 않는다는 것을 보이면, 임의의 개수의 단위 공들의 집합은 최대 2개의 기하학적 순열을 갖는다는 것을 의미하게 된다. 따라서 본 학위 논문에서는 이 두 개의 순열과 관련된 기하학적 성질에 대해 연구하였다.