|
|
Unfolding some classes of polycubes
Minařík, Josef ; Kynčl, Jan (advisor) ; Tiwary, Hans Raj (referee)
An unfolding of a polyhedron is a cutting along its surface such that the surface remains connected and it can be flattened to the plane without any overlap. An edge- unfolding is a restricted kind of unfolding, we are only allowed to cut along the edges of the faces of the polyhedron. A polycube is a special case of orthogonal polyhedron formed by glueing several unit cubes together face-to-face. In the case of polycubes, the edges of all cubes are available for cuts in edge-unfolding. We focus on one-layer polycubes and present several algorithms to unfold some classes of them. We show that it is possible to edge-unfold any one-layer polycube with cubic holes, thin horizontal holes and separable rectangular holes. The question of edge-unfolding general one-layer polycubes remains open. We also briefly study some classes of multi-layer polycubes. 1
|
|
| |
|
|
Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (advisor) ; Tiwary, Hans Raj (referee)
Graph-partitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multi-commodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called Cut-Matching game framework. Finally we present the performance results of our implementation of the Leighton-Rao and the Cut-Matching game algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Life-like system from simple particle motion
Joo, Hyungbin ; Tiwary, Hans Raj (advisor) ; Schmickl, Thomas (referee)
This thesis introduces a new software implementation of the "primordial particle sys- tem", a particle system that is remarkable for exhibiting life-like behavior with only a simple motion formula. A survey has been made of the processes, design choices, and experimentational results of the implementation. The implementation has then been as- sessed in terms of its fidelity to its motivating journal article by Schmickl et al. and also in terms of its performance and usage characteristics. 1
|
|
| |
|
|
Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (advisor) ; Tiwary, Hans Raj (referee)
Graph-partitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multi-commodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called Cut-Matching game framework. Finally we present the performance results of our implementation of the Leighton-Rao and the Cut-Matching game algorithms. Powered by TCPDF (www.tcpdf.org)
|
guest ::
