2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Please make your question a bit more specific. What are you stating? $\endgroup$
    – MPIchael
    Oct 7, 2022 at 9:49

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.