Mřížkové rozkládání ortostacků

Abstract

Ortostack je ortogonální mnohostěn vytvořený stavěním ortogonálních hranolů (pater) na sebe. Rozklad do sítě je proces, ve kterém rozřežeme povrch mnohostěnu a rozložíme ho do roviny. Popíšeme známý algoritmus pro rozklad třídy ortostacků s ortogonálně konvex- ními patry a naznačíme, proč není dostatečný pro patra libovolné výšky. Poté popíšeme známý algoritmus pro rozklad třídy ortostacků s obdélníkovými stěnami a představíme modifikaci tohoto algoritmu pro rozklad věží z kvádrů (ortostacky s obdélníkovými party). Rozzipování je speciálním typem rozkládání, kde řezné hrany tvoří jedinou cestu. Naším hlavním výsledkem je algoritmus pro rozzipování věží z kvádrů. Nakonec představíme třídu ortogonálních mnohostěnů pojmenovanou ulice s věžemi z kvádrů a ukážeme algo- ritmus pro rozklad do sítě.

An orthostack is an orthogonal polyhedron obtained by stacking orthogonal prisms (slabs) on top of each other. An unfolding is the process of cutting the surface of the polyhedron and flattening it to the plane. We describe a known algorithm for unfolding a subclass of orthostacks with orthogonally convex slabs, and we indicate why it is un- suitable for slabs of arbitrary height. Next, we describe a known algorithm for unfolding a subclass of orthostacks with rectangular faces, and we present a modification of this algorithm for unfolding box towers (orthostacks with rectangular slabs). Unzipping is a special type of unfolding whose cutting segments form a single path. As our main result, we show that every box tower has an unzipping. Finally, we introduce a subclass of orthogonal polyhedra named box towers streets and present an algorithm for unfolding.