3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Optidad
    Commented May 11, 2019 at 14:17
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented May 18, 2019 at 22:13
  • $\begingroup$ 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 $\endgroup$
    – Ignacio
    Commented May 30, 2019 at 12:30

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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