Surface-based computation of the Euler characteristic in the BCC grid
type: Item
instance of: scholarly article
title: Surface-based computation of the Euler characteristic in the BCC grid
author: Lidija Čomić
author: Paola Magillo
published in: Journal of Mathematical Imaging and Vision
publication date: 2024-01-10T00:00:00Z
review text: In this paper, the authors propose three algorithms for computing the Euler characteristic in a body-centered cubic grid. In the algorithms, the authors use a surface-based approach and propose two frameworks. The first framework is the piecewise linear critical point Morse theory. For this framework, the authors introduce an algorithm that computes the Euler characteristic of the boundary by recording the changes in the lower level sets with a suitable elevation function \(f\), defined in such a way that no two vertices have the same function value. This is done by considering the lexicographic order of the \((x, y, z)\) triplets obtained from the coordinates of all the vertices, and function \(f\) maps each vertex onto its elevation defined as its position in the sorted list of all vertices. The complexity of the algorithm is \(\mathcal{O}(n_{\partial O} \log n_{\partial O})\), where \(n_{\partial O}\) is the number of faces in the boundary \(\partial O\). The second framework is the discrete version of the Gauss-Bonnet theorem, which states that the sum of angular vertex deficits in a polyhedron is equal to \(2 \pi\) times its Euler characteristic. For this framework, the authors introduce two algorithms. In the first algorithm, they visit all vertices of the boundary, classify them to one of four classes based on the local configuration of the incident voxels, and iteratively add the corresponding contribution of the vertex to the Euler characteristics. In the second algorithm, they visit all faces of the boundary and count the number of quad faces, the number of hex faces, and the number of vertices in the boundary. Then, they compute the Euler characteristic. The complexity of both algorithms is \(\mathcal{O}(n_{\partial O})\), where \(n_{\partial O}\) is the number of faces in the boundary \(\partial O\). The authors also compare their algorithms with algorithms based on counting the number of cells, either of the 3D object or of its 2D boundary surface. The …
reviewed by: Krzysztof Gdawiec
Mathematics Subject Classification ID: 68U10
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 55U10
Mathematics Subject Classification ID: 57Q70
zbMATH DE Number: 7786048
zbMATH Keywords: digital topology
zbMATH Keywords: Euler characteristic
zbMATH Keywords: body centered cubic (BCC) grid
zbMATH Keywords: Morse theory
zbMATH Keywords: discrete Gauss-Bonnet theorem
MaRDI profile type: MaRDI publication profile
full work available at URL: s10851-023-01153-y
OpenAlex ID: W4384499719
cites work: Critical Points and Curvature for Embedded Polyhedral Surfaces
cites work: A tutorial on well-composedness
cites work: Q2763438
cites work: Digital topological method for computing genus and the Betti numbers
cites work: Repairing 3D binary images using the BCC grid with a 4-valued combinatorial coordinate system
cites work: Body centered cubic grid -- coordinate system and discrete analytical plane definition
cites work: Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds
cites work: Dual complexes of cubical subdivisions of \({\mathbb{R}}^{n}\)
cites work: Q4819371
cites work: Q5823233
cites work: Q3155868
cites work: Concepts of digital topology
cites work: A theory of binary digital pictures
cites work: Winding and Euler numbers for 2D and 3D digital images
cites work: An introduction to Morse theory. Transl. from the Japanese by Kiki Hudson and Masahico Saito
cites work: Q3874954
cites work: Morse Theory. (AM-51)
cites work: Elementary differential geometry
cites work: Digital distance functions on three-dimensional grids
cites work: Q4796927
DOI: 10.1007/S10851-023-01153-Y
description: scientific article; zbMATH DE number 7786048