| Geometric computation for cartography, realistic terrain modeling, and delineation of imprecise geographic regions all require geometric algorithms where several geometric criteria must be met simultaneously. This proposal addresses such computational problems by designing new algorithms with efficiency analyses and approximation factor proofs. In cartographic generalization, for example, spatial aggregation of two regions asks for a new, connected region that has a natural shape, but while adding as little area in the connection as possible. For metro maps, stations must be close to their true location, connections may only have few, restricted-orientation links, and connections may not intersect. Many other examples can be given in which there are several criteria that determine a good solution. In terrain modeling, conversion of an elevation grid to a polyhedral terrain (triangulation) is an important operation. The resulting triangulation is often the Delaunay triangulation because it maximizes the smallest angle used. Therefore, it is good for height interpolation. But other criteria like slope fidelity and avoiding artificial dams are also important. These problems will be studied using higher-order Delaunay triangulations. Geometric optimization problems are often NP-hard, or an optimal solution is incomputable. Allowing additional constraints will not reduce asymptotic running time. Instead, problems will become essentially more difficult. Therefore, the focus will be on efficient approximation algorithms with guaranteed performance factors. The starting point is problems with two geometric constraints where one constraint must be met using a threshold, while the other constraint is optimized. |
