Intersections tests between meshes in physics engines are time consuming and computationalheavy tasks. In order to speed up these intersection tests, each mesh can be decomposedinto several smaller convex hulls where the intersection test between each pair of these smallerhulls becomes more computationally efficient. The decomposition of meshes within the game industry is today performed by digital artistsand is considered a boring and time consuming task. Hence, the focus of this master thesislies in automatically decompose a mesh into several smaller convex hulls and to approximatethese decomposed pieces with bounding volumes of different complexity. These boundingvolumes together represents a collision mesh that is fully usable in modern games.

A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi is the subset of the edge set of G for all i which implies no additional restrictions. However, if G is not the complete graph, then this condition may have implications. We will give necessary and sufficient conditions for minimal coverings of complete bipartite graph with 6-cycles, which we call minimal unrestricted coverings. We also give necessary and sufficient conditions for minimal coverings of the complete bipartite graph with 6-cycles with the added condition the edge set of Hi is a subset of G for all i, and call these minimal restricted coverings.

The anthropogenic introduction of species into new ecosystems is a global phenomenon, and identifying the mechanisms by which some introduced species become dominant in their introduced ranges (i.e., invasive) is crucial to predicting, preventing, and mitigating the impacts of biological invasions. Introduced perennial C₄ grasses are invading semi-arid grassland and savanna ecosystems throughout the south-central U.S. We hypothesized that in these semi-arid ecosystems, where variable precipitation patterns strongly influence vegetation dynamics, the success of an invasive plant species may be due in part to ecophysiological traits that enable high performance in response to unpredictable water availability. We also hypothesized that increased primary productivity and decreased plant input quality associated with these grass invasions have the potential to alter ecosystem carbon and nitrogen cycling and storage by altering the ratio of inputs (productivity) to outputs (decomposition/respiration). We tested the first hypothesis by quantifying ecophysiological performance differences between an invasive C₄ grass, Bothriochloa ischaemum, and co-occurring C₃ and C₄ native grasses under wet and dry conditions in the field and under two levels of simulated precipitation frequencies in a greenhouse experiment. We tested the second hypothesis by examining whether increased primary productivity and decreased C₃:C₄ grass ratios in savanna grass-matrices associated with B. ischaemum invasion altered (1) plant input quality and thus nutrient cycling and/or (2) net ecosystem carbon uptake in invaded areas. B. ischaemum's success as an invader was not directly related to its ability to cope with precipitation variability and availability, but its ability to rapidly produce large amounts of biomass may allow it to directly out-compete native species. B. ischaemum invasion decreased plant input quality and soil nitrogen availability. B. ischaemum invasion shifted ecosystem C-uptake from being nearly year-round to occurring predominantly in the summer. Greater C-uptake during the summer and under drier conditions compensated for a shorter growing seasons in B. ischaemum-invaded areas and cumulative annual NEE was similar between invaded and native-dominated areas. We conclude that B. ischaemum's impacts on soil nitrogen availability and plant-canopy microhabitat may allow it to exclude native species from invaded areas, but that its impacts on ecosystem C sequestration may be small. / text

Nonnegative matrix factorization (NMF) is an important data-analysis problem which concerns factoring a given d n matrix A with nonnegative entries into matrices B and C where B and C are d k and k n with nonnegative entries. It has numerous applications including Object recognition, Topic Modelling, Hyper-spectral imaging, Music transcription etc. In general, NMF is intractable and several heuristics exists to solve the problem of NMF. Recently there has been interest in investigating conditions under which NMF can be tractably recovered. We note that existing attempts make unrealistic assumptions and often the associated algorithms tend to be not scalable. In this thesis, we make three major contributions: First, we formulate a model of NMF with assumptions which are natural and is a substantial weakening of separability. Unlike requiring a bound on the error in each column of (A BC) as was done in much of previous work, our assumptions are about aggregate errors, namely spectral norm of (A BC) i.e. jjA BCjj2 should be low. This is a much weaker error assumption and the associated B; C would be much more resilient than existing models. Second, we describe a robust polynomial time SVD-based algorithm, UTSVD, with realistic provable error guarantees and can handle higher levels of noise than previous algorithms. Indeed, experimentally we show that existing NMF models, which are based on separability assumptions, degrade much faster than UTSVD, in the presence of noise. Furthermore, when the data has dominant features, UTSVD significantly outperforms existing models. On real life datasets we again see a similar outperformance of UTSVD on clustering tasks. Finally, under a weaker model, we prove a robust version of uniqueness of NMF, where again, the word \robust" refers to realistic error bounds.