# Find plane within margin of error of >50% of points

There are $$N < 3\times10^4$$ 3D points. At least 50% of them lie approximately in the same plane, i.e. the distance between the plane and each point is at most $$p$$. Find such a plane.

Attempt: since the number of points in the plane is at least 50%, we can randomly sample 3 points from the set. They will all be in the plane with probability 12.5%. We build a plane through these 3 points and check that at least 50% of points lie approximately in it. Within 10-20 samples we'll find the plane.

Problem: because of the margin of error there's not just one plane going through 3 points, but many possible planes. How do we examine all of them?

How would you tackle this problem?

• Is this a problem with an existing solution that needs a very robust solution or is this for data analysis and you want an efficient way to get a good $p$, not necessarily the best ? – Vince May 11 at 14:17
• Can you tell us more about your problem? Is this an exercise? Is the goal to find the optimal plane, or any relatively good plane? Is this a practical problem or a theoretical one? Where did you encounter it? Can you credit the original source? – D.W. May 18 at 22:13
• Heard this problem from a friend who got it at some interview. It turned out this is a standard problem in computer vision. The standard approach is RANSAC, as @D.W. suggested – Ignacio May 30 at 12:30