Topology captures a surface’s global features invariant to local deformation, and many geometry processing applications can benefit from topological information. However, traditional topological data analysis methods, e.g., persistent homology, when applied to surfaces, suffer from their massive computation cost and their lack of exact correspondence with surface geometry. In this dissertation, we use edge cycles as a compact representation of the surface’s topology and apply it in two topological decompositions of meshes. We propose an iterative method to localize tunnel and handle cycles, which respectively capture the surface's exterior and interior spaces. We then present the tori decomposition that segments the surface into genus-1 components. We formulate the tori decomposition as a min-cut problem in the dual graph and design geometry-aware edge weights to make the decomposition fit to the geometry. We also propose a framework to decompose the surface into contractible solids. Unlike previous methods which rely on volumetric representation, we solve the problem on the surface. We find a redundant set of cycles, which form an oversegmentation of the surface, and then we apply a dynamic programming method to merge the cells to form a contractible decomposition. All of our algorithms are based on efficient surface-embedded graph algorithms, and we demonstrate their robustness on numerous models.

Point networks have recently enjoyed a lot of success due to the significant growth in 3D data and the development of novel point network architectures focusing on new applications. In this dissertation, I show that the performance of existing point networks can be improved by using insights from classical geometry processing algorithms. I demonstrate this first by proposing a new point-surface loss function called Quadric loss, which preserves sharp features such as edges and corners of 3D shapes. Inspired by the classical quadric simplification, Quadric loss minimizes the quadric error between the reconstructed points and the input surface. I show that combining Quadric loss with other popular point based loss functions can achieve better reconstruction results than existing approaches. Next, I propose a new meshing algorithm called Guided and Augmented Meshing, GAM, which generates a surface for the output points of a point network using a mesh prior. GAM decouples the geometry from the topology by making the point network solely responsible for geometry and the mesh prior responsible for topology. I show the benefits of such a disentanglement for single-view shape prediction and fair evaluation of deep point networks. Finally, I also present a novel 3D mesh dataset which was curated during this research, along with its several promising future applications.

In this dissertation, two central problems in computer science are considered:

(1) ranking n items from pairwise comparisons focussing on -

(1a) handling adversarial noise

(1b) incorporating feature information

(2) robust matrix factorization algorithms focussing on -

(2a) space-efficient computation

(2b) using feature information

Motivated by several open theoretical and practical questions, novel solutions to the above problems are explored in detail; to be specific, the contributions are summarized below:

(1) Ranking:

(Part-1a) In the presence of adversarial noise, many popular ranking algorithms, such as maximum likelihood and rank centrality, for estimating standard models, fail to work well. Robustifying many existing models such as the binary choice models, an algorithm is devised to provably recover an epsilon-accurate ranking with high probability while allowing as large as O(n) grossly corrupted comparison results per item.

(Part-1b) Typically, items have associated features. Subsuming several models including the classic Bradley-Terry-Luce and Thurstone models, a feature-based low-rank model is proposed and characterized. In learning this model, the O(n log n) sorting barrier is provably improved upon due to the proposed sample-efficient polynomial time algorithm that systematically uses features and feature correlations. Via empirical benchmarking, it is shown that the proposed approach consistently outperforms the state-of-the-art algorithms that do not use feature information.

(2) Matrix factorization:

(Part-2a) While principal component analysis and its variants are very well-studied, existing algorithms are either space-efficient or noise-tolerant; in contrast, incorporating both these aspects in solving eigen-problems, a space-efficient noise-tolerant algorithm with finite sample guarantees is developed and analyzed in the framework of the perturbed spiked covariance model under weaker assumptions than previous works; a key differentiating aspect from previous works is that the algorithm is streaming. Moreover, the derived computational and statistical guarantees are near optimal (up to logarithmic factors).

(Part-2b) While robust subspace identification methods, both convex and non-convex, are well-studied, they are often oblivious to utilizing feature information that is available in practice; in contrast to existing (feature-oblivious) convex and non-convex approaches, a simple iterative method with a fast (linear) convergence property is proposed and studied - a key aspect that differentiates this from previous works is how side information is incorporated in achieving better robust subspace recovery.

Spatially Augmented Reality (SAR), also known as projection mapping, uses multiple projectors to illuminate surfaces of arbitrary shape and size and create seamless, large-scale displays. Traditional SAR assumes that the projection surface is static and rigid. This restriction was partially addressed by Dynamic-SAR, where the surface is rigid and of known shape but can be moved around. However, no prior work has addressed SAR using multiple projectors on deformable surfaces, where the shape is unknown and constantly changing. Thus, multi-projector SAR on deformable surfaces introduces several challenges, including projector-camera calibration on a deformable surface, real-time surface shape recovery and real-time multi-projector warping and blending. My thesis is the first attempt to develop a comprehensive framework for achieving seamless multi-projector displays on deformable surfaces. Furthermore, I will also be presenting its applications in the medical domain to enable remote surgical guidance by using SAR to illuminate surgical stencils on a physical surgical site precisely.