Efficient Robust Digital Hyperplane Fitting with Bounded Error

International audienceWe consider the following fitting problem: given an arbitrary set of N points in a bounded grid in dimension d, find a digital hyperplane that contains the largest possible number of points. We first observe that the problem is 3SUM-hard in the plane, so that it probably cannot be solved exactly with computational complexity better than O(N 2), and it is conjectured that optimal computational complexity in dimension d is in fact O(N d ). We therefore propose two approximation methods featuring linear time complexity. As the latter one is easily implemented, we present experimental results that show the runtime in practice