Improved Upper Bounds for Polygon Containment and Elastic Geometric Shape Matching Pohang University of Science and Technology

Abstract

While there are many measures of algorithmic performance, the most common and popular is asymptotic analysis. This is because it accounts for limiting behavior and can provide a meaningful representation of the performance of a general algorithm. As a result, reducing time or space complexity is one of the most important goals in algorithm design. In this thesis, we consider some geometric optimization problems and propose improved upper bounds of time complexities. The first optimization problem is finding a maximum-area convex polygon inscribed in a given domain. The domain that we consider can be a convex polygon, a simple polygon, or a polygonal domain consists of line segments and points and the convex polygon wants to find is rectangle, various types of triangles, or a prescribed convex polygon. The results can be summarized as follows: An O(n3 log n) time and O(kn2 + n) space algorithm for the problem of finding a maximum-area rectangle in a simple polygon with n vertices, where k is the number of reflex vertices. For the problem of finding a maximum-area triangles with fully or partially fixed angles in a convex or simple polygon with fixed or arbitrary orientation, there are several results, but for the case of fully fixed angle, arbitrary orientation, and simple polygon with n vertices, O(n2 log n) time and linear space algorithms is proposed. For the problem of finding a largest similar copy of convex polygon with k vertices in a polygonal domain with n elements, we present an O(k2n2λ4(k) log n) time algorithm, where λs(n) is the length of the longest Davenport-Schinzel sequence of order s including n distinct symbols. The second problem is elastic geometric shape matching under translation and the Euclidean distance measure. For a given point set and a neighborhood graph, the goal is to find the translation-ensemble that minimizes both the distance from point to translation and the distance between two translation corresponding to an edge of the neighborhood graph. O(ε−2n2 log n) time (1 + ε)-approximation algorithm for the general neighborhood graph and O(ε−1 log ε−1n log n) time (1 + ε)-approximation algorithm for a cycle neighborhood graph are proposed, where n is the number of points in the point set.