Geometric Algorithms (TODO)

Smallest Enclosing Circle

Let $P$ be a given set of $n$ points on a plane. We want to find the circle $C (P)$ such that $C (P)$ encloses all points in $P$ and such that the radius of $C (P)$ is as small as possible. For a circle $C$ we denote by $C^{∙}$ the circular disk which is enclosed by $C$ (closed, thus including $C$ ). We allow points in $P$ to also lie on $C (P)$ - they do not have to lie strictly within the circle.

📌 For every (finite) set of points $P$ in $R^{2}$ there exists a unique smallest enclosing circle $C (P)$ .

📌 For every (finite) set of points $P$ in $R^{2}$ with $∣ P ∣ \geq 3$ there exists a subset $Q \subseteq P$ such that $∣ Q ∣ = 3$ and $C (Q) = C (P)$ .

This lemma immediately allows a $O (n^{4})$ -time algorithm for computing $C (P)$ . We can then introduce a bit of randomization to the algorithm to try to optimize it a little, which fails however as they still both have the same asymptotic time complexity:

Untitled

We could try to draw more than just 3 points in each iteration to have a higher chance of including the 3 defining points, to for example 11 points instead. This however effects no change in the asymptotic runtime, as one can verify. To really speed up the computation we can introduce another key idea: we weight the points outside the of $C (Q)$ doubly in every iteration.

Untitled

📌 Let $n_{1}, \dots, n_{t}$ be natural numbers and $N = \sum_{i = 1}^{t} n_{i}$ .

We generate $X \in {1, \dots, t}$ randomly as follows:

Untitled

It then holds that $Pr [X = i] = \frac{n _{i}}{N}$ for all $i = 1, \dots, t$ .

With this lemma we can thus draw points from $P$ in such a way that the probability of a point is proportional to the number of its copies. If we now respect points we’ve already drawn then we can compute our desired subset $Q$ consisting of 11 points of $P$ in $O (n)$ .

📌 Let $P$ be a set of $n$ (not necessarily distinct) points and for $r \in R$ let $R$ be randomly, uniformly distributed in $(r P)$ . Then the expected number of points of $P$ that are outside of $C (R)$ is at max $3 \frac{n - r}{r + 1} \leq 3 \frac{n}{r + 1}$ .

📖 The algorithm $Randomized_CleverVersion$ computes the smallest enclosing circle of $P$ in expected time $O (n lo g n)$ .

This algorithm is a variation of the algorithm of Clarkson. There exist randomized algorithms that compute $C (P)$ optimally in linear time.

Sampling Lemma

💡 Let $S$ be a finite set with $n$ elements and let $ϕ$ be an arbitrary function on $2^{S}$ into an arbitrary codomain. We define

$V (R) = V_{ϕ} (R) X (R) = X_{ϕ} (R) = {s \in S ∣ ϕ (R \cup {s}) \neq = ϕ (R)} = {s \in R ∣ ϕ (R ∖ {s}) \neq = ϕ (R)} .$

We call elements in $V (R)$ violators of $R$ and elements in $X (R)$ extreme in $R$ .

We can see that $s \in V (R) ⟺ s \in X (R \cup {s})$ . Our goal is to gather understanding about how big $V (R)$ is when $R$ is randomly chosen with given $r$ .

Example: Smallest Number

Let $A \subseteq N$ be a finite subset of the naturals. For $R \subseteq A$ let $ϕ (R) = min (R)$ , with $min \emptyset = \infty$ . The following holds:

$X (R) = {min (R)}$ (for $R \neq = \emptyset$ )
$V (R) = {a \in A ∣ a < min (R)}$ .

Clearly, for $R \neq = \emptyset$ it holds that $∣ X (R)∣ = 1$ and $∣ V (R)∣$ is the amount of elements in $A$ that are smaller than $min (R)$ , i.e., $∣ V (R)∣ + 1$ is the rank of $min (R)$ in $A$ , where the rank of $a \in A$ is the index of $a$ in the ascendingly sorted sequence of elements of $A$ .

Example: Smallest Enclosing Circle

Let $P$ be a finite set of points. For $R \subseteq P$ let $ϕ (R) = C (R)$ be the smallest enclosing circle of $R$ (with $ϕ (\emptyset) = \emptyset$ ). $V (R)$ is exactly the set of points outside of $C (R)$ and we already saw that $∣ X (R)∣ \leq 3$ .

The sampling lemma relates the number of violating elements to the number of extreme elements.

📌 (Sampling Lemma).

Let $k \in N, 0 \leq k \leq n$ . We set $v_{k} = E [∣ V (R)∣]$ and $x_{k} = E [∣ X (R)∣]$ , where $R$ is a subset of $S$ with $k$ elements that is random, uniformly distributed from $(k S)$ . The for $r \in N, 0 \leq r < n$ it holds that

$\frac{v _{r}}{n - r} = \frac{v _{r + 1}}{r + 1} .$

📎 If we choose $r$ elements $R$ from a set $A$ of $n$ numbers randomly, then the expected rang of the minimum of $R$ in $A$ exactly $\frac{n - r}{r + 1} + 1 = \frac{n + 1}{r + 1}$ .

If we choose $r$ points $R$ from a set $P$ of $n$ points in a plane randomly, then the expected number of points of $P$ outside of $C (R)$ is at max $3 \frac{n - r}{r + 1}$ .

Geometric Algorithms (TODO)

Smallest Enclosing Circle

Sampling Lemma

Example: Smallest Number

Example: Smallest Enclosing Circle

Convex Closure