Thesis (M. Sc.)--Carleton University, 2004. / Includes bibliographical references (p. 95-99). Also available in electronic format on the Internet.

In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the edge isoperimetric value of G at I be defined as be(i,G)= mins v;|s|= i | δ(S,G)|. For S V, let φ(S,G) = {u ε V – S : ,such that be the vertex boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the vertex isoperimetric value of G at I be defined as bv(i,G)= The edge isoperimetric peak of G is defined as be(G) =. Similarly the vertex isoperimetric peak of G is defined as bv(G)= .The problem of determining a lower bound for the vertex isoperimetric peak in complete k-ary trees of depth d,Tdkwas recently considered in[32]. In the first part of this thesis we provide lower bounds for the edge and vertex isoperimetric peaks in complete k-ary trees which improve those in[32]. Our results are then generalized to arbitrary (rooted)trees. Let i be an integer where . For each i define the connected edge isoperimetric value and the connected vertex isoperimetric value of G at i as follows: is connected and is connected A meta-Fibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n-1))+ a(x2(n)+ a2′(n -2)), where xi: Z+ → Z+ , i =1,2, is a linear function of n and ai′(j)= a(j) or ai′(j)= -a(j), for i=1,2. Sequences belonging to this class have been well studied but in general their properties remain intriguing. In the second part of the thesis we show an interesting connection between the problem of determining and certain meta-Fibonacci sequences. In the third part of the thesis we study the problem of determining be and bv algorithmically for certain special classes of graphs. Definition 0.1. A tree decomposition of a graph G = (V,E) is a pair where I is an index set, is a collection of subsets of V and T is a tree whose node set is I such that the following conditions are satisfied: (For mathematical equations pl see the pdf file)

This thesis is dedicated to ray tracing based rendering methods, primarily the original ray tracing. Besides introducing a brief historical overview of algorithms from the family, it presents all the essential tools, techniques and physics needed for designing a rendering application in detail. A significant part of the document consists of an implementation of a photorealistic rendering application for interactive graphics 3D virtual scenes. The focus is on rendering without using any additional model information. The thesis includes descriptions and explanations of specific problems and their solutions.

Level sets are extensively used for the visualization of scalar fields. The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. It is obtained by mapping each connected component of a level set to a point. The Reeb graph and its loop-free version called the contour tree serve as an effective user interface for selecting meaningful level sets and for designing transfer functions for volume rendering. It also finds several other applications in the field of scientific visualization. In this thesis, we focus on designing algorithms for efficiently computing the Reeb graph of scalar functions and using the Reeb graph for effective visualization of scientific data. We have developed three algorithms to compute the Reeb graph of PL functions defined over manifolds and non-manifolds in any dimension. The first algorithm efficiently tracks the connected components of the level set and has the best known theoretical bound on the running time. The second algorithm, utilizes an alternate definition of Reeb graphs using cylinder maps, is simple to implement and efficient in practice. The third algorithm aggressively employs the efficient contour tree algorithm and is efficient both theoretically, in terms of the worst case running time, and practically, in terms of performance on real-world data. This algorithm has the best performance among existing methods and computes the Reeb graph at least an order of magnitude faster than other generic algorithms. We describe a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. We also employ the Reeb graph in four different applications – surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data. Finally, we introduce the notion of topological saliency that captures the relative importance of a topological feature with respect to other features in its local neighborhood. We integrate topological saliency with Reeb graph based methods and demonstrate its application to visual analysis of features.