| The partitioning and covering problems are very fundamental in combinatorial optimization and applications. In this dissertation, we consider a number of partitioning and covering problems, most of which are of interdisciplinary nature, such as optimal polygon cover problems, k-terminal cuts on planar graphs, pairwise data clustering, optimal net surface problems, and optimal terrain construction problems. These problems find applications in many fields, e.g., radiation therapy and radio-surgery, biomedical image analysis, data mining, VLSI circuit design, networking, computer vision, surface reconstruction, and material layout. Several general geometric and combinatorial techniques and algorithmic frameworks for solving these problems have been invented. Most of our algorithms are based on judicious combinations of geometric techniques, graph theory, and operations research. Our algorithms are either the first ones for solving the corresponding problems, or they significantly improve the previous best known algorithms, with respect to the time complexity and/or the quality of the output solutions. |
