# Min supporting line of a set of points

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?

• Please make your question a bit more specific. What are you stating? Commented Oct 7, 2022 at 9:49

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.