Advanced STG decomposition [Elektronische Ressource] / vorgelegt von Mark Schäfer

AdvancedSTGDecompositionDissertation zur Erlangung des Grades einesDoktors der Naturwissenschaften (Dr. rer. nat)der Fakult¨at fu¨r Angewandte Informatikder Universit¨at AugsburgVorgelegt vonMark Sch¨aferGutachterErstgutachter: Prof. Dr. Walter VoglerZweitgutachter: Prof. Dr. Bernhard M¨ollerMu¨ndliche Pru¨fung28. Februar 2008To my wife Maren and my daughter CharlotteI would like to thank everybody who supported and entertained meduring this four years and all the years before.Thank you all!Brina, as ever — Elmar, for explaining objects — Frank, for pizzaGabriele, for all that libraries — Heinz, for bed and breakfast — Hilli, for smokingJan & Thomas, for ma¨a¨a¨a¨a¨a¨h — Jonathan & Victor, for many discussionsJu¨rgen, for da brainz — Minna, for math — Peter, for the gamesStephan, for the ketchup — Ute, for the fun — Walter, for being senseiWerner, for showing the way — Willi, for weldingAdvanced STG DecompositionAdvancedSTGDecompositionMark SchaeferUniversity of AugsburgBibliografische Information der Deutschen NationalbibliothekDie Deutsche Nationalbibliothek verzeichnet diese Publikation in derDeutschenNationalbibliografie; detaillierte bibliografische DatensindimInternet ub¨ er http://dnb.d-nb.de abrufbar.°c 2008 Mark Schaefermark@markschaefer.deHerstellung und VerlagBooks on Demand GmbH, NorderstedtISBN: 978-3-8370-4604-5CONTENTSContents1 Introduction 111.1 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .