Digital Hyperplane Fitting

摘要

This paper addresses the hyperplane fitting problem of discrete points in any dimension (i.e. in Z~d). For that purpose, we consider a digital model of hyperplane, namely digital hyperplane, and present a combinatorial approach to find the optimal solution of the fitting problem. This method consists in computing all possible digital hyperplanes from a set S of n points, then an exhaustive search enables us to find the optimal hyperplane that best fits S. The method has, however, a high complexity of O(n~d), and thus can not be applied for big datasets. To overcome this limitation, we propose another method relying on the Delaunay triangulation of S. By not generating and verifying all possible digital hyperplanes but only those from the elements of the triangulation, this leads to a lower complexity of O(n~(「d/2」 + 1)). Experiments in 2D, 3D and 4D are shown to illustrate the efficiency of the proposed method.