Date of Award
2003
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Computer Science.
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
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.
Recommended Citation
Zhang, Hongtao., "On finding a maximum empty rectangle of arbitrary orientation: Theory and implementation." (2003). Electronic Theses and Dissertations. 2917.
https://scholar.uwindsor.ca/etd/2917