Geometric optimization, which has emerged as an important line of research within the field of Computational Geometry, is concerned with computational problems in which the objective is to find the best of all possible solutions. More formally, it is used to find an optimal solution with the minimum (or maximum) value in a search space which contains all the possible solutions. In this thesis, we begin with a very brief survey of the field of geometric optimization, focussing on the some of the important techniques that have been used to solve a variety of problems in this area. Then, we study a particular geometric optimization problem that has been the focus of our work: finding an empty rectangle of arbitrary orientation among a set of n points in the plane. We review an O(n 3) time algorithm for finding the Largest Empty Arbitrary Oriented Rectangle (LEAOR) due to [MR03], and describe the details of an implementation of this algorithm that we have done. We also discuss the problem of finding an LEAOR when the edges of the bounding rectangle is taken into account, and suggest an approximation approach to this problem. Source: Masters Abstracts International, Volume: 42-02, page: 0626. Thesis (M.Sc.)--University of Windsor (Canada), 2003.
展开▼
