Our goal is to compute reliable solutions for many non-linear geometric problems that arise in geometric modeling, computer graphics and robotics. Prior methods for solving these problems can be classified into exact and approximate approaches. The exact algorithms are able to guarantee correct output, but are usually difficult to implement reliably and efficiently. On the other hand, current approximate techniques may not provide any topological guarantees on the solution. We bridge the gap between these two approaches, by developing a unified sampling based approach to solve these problems with topological guarantees. Specifcally, we present results for surface extraction and motion planning problems. Surface extraction problems include Boolean operations, implicit surface polygonization and Minkowski sum evaluation. We compute an approximate boundary of the final solid defined by these operations. Our algorithm computes an approximation that is guaranteed to be topologically equivalent to the exact surface and bounds the approximation error using two-sided Hausdorff error. We demonstrate the performance of our approach for the following applications: Boolean operations on complex polyhedral models and low degree algebraic primitives, model simplification and remeshing of polygonal models, and Minkowski sums and offsets of complex polyhedral models. The second class of problems is motion planning of rigid or articulated robots translating or rotating among stationary obstacles. We present an algorithm for complete motion planning, i.e., find a path if one exists and report a failure otherwise. Our algorithm performs deterministic sampling to compute a roadmap that captures the connectivity of the free space and combines with randomized sampling and cell decomposition to further improve the performance. We demonstrate the performance of our algorithm on a number of challenging environments with narrow passages and no collision-free paths.