CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-07247S" target="_blank" >GA18-07247S: Metody a algoritmy pro analýzu obrazů vektorových a tenzorových polí</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Kybernetika

ISSN

0023-5954

e-ISSN

—

Svazek periodika

55

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

CZ - Česká republika

Počet stran výsledku

27

Strana od-do

755-781

Kód UT WoS článku

000509991200001

EID výsledku v databázi Scopus

2-s2.0-85079682794