Min supporting line of a set of points

Question

I am following along Rourke's book and I am trying to do the excercies mentioned in this SO post:

Min supporting line for a set of points

Design an algorithm to find a line 𝐿 that:

has all the points of a given set to one side

minimizes the sum of the perpendicular distances of the points to 𝐿 Assume a hull algorithm is available.

Just like the OP in that question I also solved the problem when the set is just the convex hull. You can easily make an h log h algorithm for the hull that finds you a line and a point in the hull such that their distance is the smallest among all possible such pairs.

You just:

• start a given line in the hull
• Look at the point that is h / 2 indices away in the CCW direction
• if both points adjacent to this point are closer to the line, mark this line point pairing.
• else, see which point is farther away and look at the median index of the range between your line endpoints and the point you just found.
• Repeat until you've found the farthest point from the line.
• Repeat for every line to find the line point pair that minimizes the distance.

The search operation is logarithmic so this takes $h \log h$. If your set of points is the hull I am 100% sure this minimizes the distances.

But I am not convinced that this is the optimal solution for any set of points however.

Consider a really, really, really, narrow triangle. let $P_1, P_2, P_3$ be its vertices such that $P_2$ is the point that minimizes the convex hull distance.

Now let's add a billion points along the edge $P_2, P_3$ such that no 2 points share the same coordinate.

The convex hull is the same. But the edge that you should pick is $(P_2, P_3)$.

Am I wrong?

Answer 1

Given a set of $n$ points $\mathcal{P}$ in the 2-dimensional plane, consider the convex hull $\text{chull}(\mathcal{P}) = p_1 p_2 \dots p_h p_1$, with the boundary represented as a cycle comprised of $h$ points from $\mathcal{P}$. The line $L$ that we are after must correspond to one of the edges on the hull (why?). For any edge $e = \{p, p'\}$ on the hull, let its inward pointing normal be $n_e$. We want to find an edge $e$ on the hull that minimizes the sum of perpendicular distances from the edge, namely $\sum_{x \in \mathcal{P}} (x - p) \cdot n_e$. We can rewrite this objective like so: $$\begin{align*} \sum_{x \in \mathcal{P}} (x - p) \cdot n_e &= n_e \cdot \left(\sum_{x \in \mathcal{P}} (x - p)\right) \\ &= n_e \cdot \left(\left(\sum_{x \in \mathcal{P}} x\right) - |\mathcal{P}| p\right) \\ &= |\mathcal{P}| n_e \cdot \left(\frac{\sum_{x \in \mathcal{P}} x}{|\mathcal{P}|} - p\right) \end{align*}$$ This observation gives us a way to solve this problem efficiently. After computing the convex hull, we can compute the average of the points $\bar{x} = |\mathcal{P}|^{-1}\sum_{x \in \mathcal{P}} x$ in $O(n)$ time and store it. Then, for each edge $e$ on the convex hull, compute $n_e \cdot (\bar{x} - p)$ and keep track of the edge $e$ that minimizes this quantity. This will overall require $O(h)$ time. After identifying the optimal edge $e^*$, just construct the corresponding line $L$ with whatever format needed and return this, which should require $O(1)$ time. Using Chan's algorithm, this implies the overall runtime is $O(n \log(h) + n + h) = O(n \log(h))$, meaning the algorithm runtime is dominated by the convex hull computation.