Skip to Main content Skip to Navigation
Conference papers

Digital hyperplane fitting

Phuc Ngo 1 
1 ADAGIO - Applying Discrete Algorithms to Genomics and Imagery
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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 triangula-tion, 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.
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Phuc Ngo Connect in order to contact the contributor
Submitted on : Thursday, June 25, 2020 - 10:45:03 AM
Last modification on : Wednesday, November 3, 2021 - 7:57:41 AM
Long-term archiving on: : Wednesday, September 23, 2020 - 3:57:02 PM


Files produced by the author(s)



Phuc Ngo. Digital hyperplane fitting. 20th International Workshop on Combinatorial Image Analysis (IWCIA), Jul 2020, Novi Sad, Serbia. pp.164-180, ⟨10.1007/978-3-030-51002-2_12⟩. ⟨hal-02586206⟩



Record views


Files downloads