| Computational geometry is a discipline that deals with the complexity of geometric problems within the framework of design and analysis of algorithms. In this thesis, we study two very important and closely related classes of problems in computational geometry, namely, location problems and distance problems. These problems originated mainly from operations research and computer-aided design. For location problems, we present an optimal algorithm for the 1-line-center problem, and an efficient solution for a competitive location problem. For distance problems, we present efficient algorithms for the following three problems: (1) shortest paths and minimum spanning trees in the presence of obstacles, (2) Voronoi diagram in the presence of obstacles, and (3) minimal Steiner tree approximation. Emphases are placed on the application of efficient data structures and algorithmic techniques in problem solving, and exploring methods of problem transformations to establish lower bounds for geometric problems. |
