Combinatorical and Algebraic Structures Seminar
Session details
| Date: | 14.3.2017 |
| Speaker: | Cyril Höschl, Ústav teorie informace a automatizace AV ČR, v.v.i. |
| Title: | Polynomial heuristic method for rectangular decomposition of 3D shapes |
| Abstract: | A novel algorithm for a decomposition of 3D binary shapes to rectangular blocks will be presented. The aim is to minimize the number of blocks. Theoretically the optimal algorithm is known to be NP-hard and practically infeasible. We introduce polynomial sub-optimal heuristics, which transforms the decomposition problem onto a graph-theoretical problem. We show by extensive experiments that the proposed method outperforms state of the art methods like the octree decomposition, the run-length encoding or the binary search partitioning in terms of the number of blocks on statistically significant level. We also discuss potential applications of the method in image processing. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož