Studies of geometric optimization and proximity problems.

摘要

In this dissertation, two new problems are added to the discipline of geometric optimization, and the third one to the discipline of proximity. The first problem deals with the Minimum Radial Separation center, a standard recommended by the American National Standards Institute (ANSI) to measure the Out-of-Roundness of a polygon. The second problem deals with the Minimum Area Difference center, which can be used for the same purpose. The geometric characteristics of the two centers are studied, and applied to their computation. The third problem deals with the farthest neighbor problem for a set of multi-weighted sites. The proximity problem is studied by extending an original construct known as the Voronoi diagram to a new form called the multiplicative weighted farthest neighbor Voronoi diagram. The computation of the new construct is shown to be less complex than the multiplicative weighted nearest neighbor Voronoi diagram.