Geometric permutations of non-overlapping unit balls in $R^d$

Abstract

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.