Geodesic
Close-to-optimal algorithm for rectangular decomposition of 3D shapes
Kybernetika, Tome 55 (2019) no. 5, pp. 755-781 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, we propose a novel algorithm for a decomposition of 3D binary shapes to rectangular blocks. The aim is to minimize the number of blocks. Theoretically optimal brute-force algorithm is known to be NP-hard and practically infeasible. We introduce its sub-optimal polynomial heuristic approximation, which transforms the decomposition problem onto a graph-theoretical problem. We compare its performance with the state of the art Octree and Delta methods. We show by extensive experiments that the proposed method outperforms the existing ones in terms of the number of blocks on statistically significant level. We also discuss potential applications of the method in image processing.
In this paper, we propose a novel algorithm for a decomposition of 3D binary shapes to rectangular blocks. The aim is to minimize the number of blocks. Theoretically optimal brute-force algorithm is known to be NP-hard and practically infeasible. We introduce its sub-optimal polynomial heuristic approximation, which transforms the decomposition problem onto a graph-theoretical problem. We compare its performance with the state of the art Octree and Delta methods. We show by extensive experiments that the proposed method outperforms the existing ones in terms of the number of blocks on statistically significant level. We also discuss potential applications of the method in image processing.
DOI : 10.14736/kyb-2019-5-0755
Classification : 65D18
Keywords: 3D binary object; voxels; decomposition; rectangular blocks; sub-optimal algorithm; tripartite graph; maximum independent set 
@article{10_14736_kyb_2019_5_0755,
     author = {H\"oschl IV, Cyril and Flusser, Jan},
     title = {Close-to-optimal algorithm for rectangular decomposition of {3D} shapes},
     journal = {Kybernetika},
     pages = {755--781},
     year = {2019},
     volume = {55},
     number = {5},
     doi = {10.14736/kyb-2019-5-0755},
     zbl = {07177915},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2019-5-0755/}
}
TY  - JOUR
AU  - Höschl IV, Cyril
AU  - Flusser, Jan
TI  - Close-to-optimal algorithm for rectangular decomposition of 3D shapes
JO  - Kybernetika
PY  - 2019
SP  - 755
EP  - 781
VL  - 55
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2019-5-0755/
DO  - 10.14736/kyb-2019-5-0755
LA  - en
ID  - 10_14736_kyb_2019_5_0755
ER  - 
%0 Journal Article
%A Höschl IV, Cyril
%A Flusser, Jan
%T Close-to-optimal algorithm for rectangular decomposition of 3D shapes
%J Kybernetika
%D 2019
%P 755-781
%V 55
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2019-5-0755/
%R 10.14736/kyb-2019-5-0755
%G en
%F 10_14736_kyb_2019_5_0755
Höschl IV, Cyril; Flusser, Jan. Close-to-optimal algorithm for rectangular decomposition of 3D shapes. Kybernetika, Tome 55 (2019) no. 5, pp. 755-781. doi: 10.14736/kyb-2019-5-0755

Cité par Sources :