How we can find a straight line so that at least p percent of the points are exactly on that line?

Question

For N points on the plane, how we can determine that there is a straight line such that at least $p(20<=p<=100)$ percent of the points are exactly on that line?

For example: With $n=5,p=55$ and coordinates of $5$ points:

• 0 0
• 10 10
• 10 0
• 0 10
• 3 3

The answer is possible (it means existing a straight line satisfied problem, that's line: $y=x$,because we have $(0,0),(10,10),(3,3)$ are in this line and these points occupies $60\text{%}>55\text{%}$ of total points)

This is my try: I try build all lines that through two points of $n$ points and compute each case, but it's too waste time when $n$ is large!

Answer 1

We can solve this in expected $O(n/p^2)$ time with a randomized algorithm. Pick two distinct points at random, and see if the line through them passes through at least $p$ fraction of the points. If not, repeat. The check takes $O(n)$ time to visit all the points, and the probability that both of the chosen points are on the line is $p^2$, so we will iterate the procedure an expected $1/p^2$ times.

This algorithm only returns true positives, but if you don't know a priori that such a line exists, you can cut it off after some number of iterations to get high confidence that no such line exists.

---

The problem of finding a short algorithm to the nonexistence of a "heavy line" among the points can be connected to some graph theory as follows. Suppose the algorithm decides to visit the pairs $(p_i,p_j)\in E$ for some set $E$, and check that none of the resulting lines are heavy (that is, they do not hit $p$ fraction of all the points). This takes time $O(n|E|)$ to check by the obvious method. This forms a graph $G=(V,E)$ with the points as vertices and $E$ as the edges.

But now consider the complement graph $G^c$ which uses all the edges not in $E$. This is the graph of all pairs that were skipped in the algorithm. If the algorithm did not detect a heavy line even though one exists, then since every pair of points in the line would witness it they must all be in $G^c$. Thus $G^c$ contains a clique of size $pn$. So it suffices to ensure that $G^c$ has no cliques of size $pn$ to ensure correctness.

By Turán's theorem, a graph with no cliques of size $r+1$ (where $r=pn-1$) has at most $(1-1/r)n^2/2$ edges, hence $G$ has at least $n^2/2r=n/2p+O(1)$ edges. The theorem also gives a concrete graph, the Turán graph, that achieves this bound. So we can find a heavy line or prove nonexistence deterministically in $O(n^2/p)$ time.

Answer 2

You can solve it in $O(n^2)$ time, assuming your coordinates are rational. If they are real (and have to deal with floating point inaccuracies) it will take $O(n^2 \log n)$ time.

This is because we'll be using a multiset data structure. In the case of rational numbers I assume the existence of an efficient hash function that allows us to guarantee $O(1)$ insertion and $O(1)$ time getting the count of the most common element. When that hash function doesn't exist you can do the same with a multiset based on trees, but the time guarantee for insertion goes down to $O(\log n)$.

Given that, what is the algorithm? For each point $p$ you initialize an empty multiset and loop over all other points $q$. Compute slope $\frac{q_y - p_y}{q_x - p_x}$ and insert into the multiset. After you're done looping you request how many times the most common element in the multiset exists. If this is greater than $np/100$, you can find the line from the slope and $p$ and return it.