ROUGH DRAFT authorea.com/105589

# Assignment 2

Supplementary image to Q1.

# Fat Points

Proof by contradiction. Assume that the line segment between points $$P,Q$$ has maximum pairwise distance, and that $$Q$$ does not lie on a vertex. Let the point on the boundary of our hull found by extending the line $$PQ$$ be denoted $$Q'$$. This boundary segment is defined between two vertices on our convex hull which we refer to as $$A$$ and $$B$$. See $$\mathbf{Fig. 1}$$ for clarification.

## Q Lies on the Interior of the Hull

Clearly $$|PQ'|>|PQ|$$. In the following section we show that there is always a line-segment longer than $$|PQ'|$$. By the transitive property of inequality this segment must also be longer than $$PQ$$, a contradiction.

## Q Lies on a Hull Edge

In this case, $$Q=Q^{\prime}$$. Observe the angles $$\angle PQ^{\prime}A$$ and $$\angle PQ^{\prime}B$$. WLOG assume $$\angle PQ^{\prime}B$$ is the larger of the two and denote it $$\alpha$$.

\begin{align} \angle PQ^{\prime}A+\angle PQ^{\prime}B & =\pi\notag \\ \therefore\alpha:=\max\left(PQ^{\prime}A,PQ^{\prime}B\right) & \geq\frac{\pi}{2}\notag \\ \end{align}

As such $$\alpha$$ must be the unique largest internal angle in the triangle $$PQ^{\prime}B$$. Consequently the side opposite $$\alpha$$ $$\left(PB\right)$$ is the unique hypotenuse of the triangle. As such $$|PB|>|PQ^{\prime}|$$. However $$P$$ and $$B$$ are both elements of the convex hull so we have found a line segment with length larger than our assumed maximum, a contradiction.

Points of comparison when inserting an interval into the heap.

# Points and Planes

We do the exact same thing as the visible-intersection problem in class: radial sweep with a heap.

## Algorithm and Runtime

• Create a set $$\mathcal{P}$$ of $$O(n)$$ points and $$O(m)$$ interval end-points: $$O(m+n)$$.
• Find the point $$m$$ with minimum distance to $$q$$: $$O(m)$$.
• Sort $$\mathcal{P}$$ by angle measured from the line segment $$qm$$. If there are multiple non-interval points with the same angle, only include the closest: $$O((m+n)\log (m+n))$$.
• Iterate through these points: $$O(m+n)$$
• If it's the first end-point of an interval, add the interval to our heap. If it's the second end-point, remove it: $$O (log(m))$$
• If it's a point, emit if it's closer than the min-heap value: $$O(1)$$

Total running time $$O((m+n)\log (m+n))$$.