The need to compactly represent 3D data is motivated by the ever-increasing size of these data. Furthermore, for large data sets it is useful to randomly access and process a small part of the data. In this thesis we propose two methods of compactly representing 3D data while allowing random access. The first is the multiresolution sphere-packing tree (MSP-tree). The MSP-tree is a multiresolution 3D hierarchy on regular grids based on sphere-packing arrangements. The grids of the MSP-tree compactly represent underlying point-sampled data by using more efficient grids than existing methods while maintaining high granularity and a hierarchical structure that allows random access. The second is distance-ranked random-accessible mesh compression (DR-RAMC). DR-RAMC is a lossless simplicial mesh compressor that allows random access and decompression of the mesh data based on a spatial region-of-interest. DR-RAMC encodes connectivity based on relative proximity of vertices to each other and organizes both this proximity data and vertex coordinates using a k-d tree. DR-RAMC is insensitive to a variety of topological mesh problems (e.g. holes, handles, non-orientability) and can compress simplicial meshes of any dimension embedded in spaces of any dimension. Testing of DR-RAMC shows competitive compression rates for triangle meshes and first-ever random accessible compression rates for tetrahedral meshes. / Thesis (Ph.D, Computing) -- Queen's University, 2012-07-17 15:28:39.406

Finding the shortest tour visiting all given points at least ones belongs to the most famous optimization problems until today [travelling salesman problem (TSP)]. Optimal solutions exist formany problems up to several ten thousand points. Themajor difficulty in solving larger problems is the required computational complexity. This shifts the research from finding the optimum with no time limitation to approaches that find good but sub-optimal solutions in pre-defined limited time. This paper proposes a new approach for two-dimensional symmetric problems with more than a million coordinates that is able to create good initial tours within few minutes. It is based on a hierarchical clustering strategy and supports parallel processing. In addition, a method is proposed that can correct unfavorable paths with moderate computational complexity. The new approach is superior to state-of-the-artmethods when applied to TSP instances with non-uniformly distributed coordinates.