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

https://hal.inria.fr/hal-02586206
Contributor : Phuc Ngo <>
Submitted on : Thursday, June 25, 2020 - 10:45:03 AM
Last modification on : Monday, March 22, 2021 - 4:50:05 PM
Long-term archiving on: : Wednesday, September 23, 2020 - 3:57:02 PM

File

paper01.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

73

Files downloads

363