CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F19%3A00518087" target="_blank" >RIV/67985556:_____/19:00518087 - isvavai.cz</a>
Result on the web
<a href="https://www.kybernetika.cz/content/2019/5/755" target="_blank" >https://www.kybernetika.cz/content/2019/5/755</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.14736/kyb-2019-5-0755" target="_blank" >10.14736/kyb-2019-5-0755</a>
Alternative languages
Result language
angličtina
Original language name
CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES
Original language description
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 suboptimal 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 signifficant level. We also discuss potential applications of the method in image processing.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA18-07247S" target="_blank" >GA18-07247S: Methods and Algorithms for Vector and Tensor Field Image Analysis</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Kybernetika
ISSN
0023-5954
e-ISSN
—
Volume of the periodical
55
Issue of the periodical within the volume
5
Country of publishing house
CZ - CZECH REPUBLIC
Number of pages
27
Pages from-to
755-781
UT code for WoS article
000509991200001
EID of the result in the Scopus database
2-s2.0-85079682794