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?

One reasonable approach is to use RANSAC.

Pick three points. Find the plane that goes through them. Iterate through all the points and keep the points that are near that plane (the inliers) and discard the rest (the outliers). If fewer than 50% of the points are inliers, discard this plane. Otherwise, discard the plane you have so far and use linear regression to find the best plane that fits the inliers as well as possible. That's a candidate plane.

Repeat this 1000 times, to get 1000 candidate planes. Take the best one. You can measure how good a candidate plane is by taking the average distance from the plane to each point, averaged over all the points that are close to that plane (ignore the ones that are far away; if 50% or more are far away, discard the plane).

StackExchange Computer Science Q#109231, answer score: 2