Author’s Archive: tcs

Home / tcs
4 Posts

Shape matching is an important ingredient in shape retrieval, recognition and classification, alignment and registration, and approximation and simplification. In a large database of shapes, for example, shape retrieval searches for all shapes similar to a query shape.

In geometric shape matching, we are given two geometric objects and compute the similarity of them based on some geometric similartity measure. In most cases, we transform one of them over the other, by scaling, translation, and rotation. Shape matching algorithms provide fundamental techniques for shape recognition and retrieval, and shape classification for large scaled shape databases. They are also used in shape alignment and registration.


Maximizing the Overlap of Two Planar Convex Sets under Rigid Motions

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any eps>0, we compute a rigid motion such that the area of overlap is at least 1-eps times the maximum possible overlap. Our algorithm uses O(1/eps) extreme point and line intersection queries on Pand Q, plus O((1/eps2)log(1/eps)) running time. If only translations are allowed, the extra running time reduces to O((1/eps)log(1/eps)). If P and Q are convex polygons with n vertices in total that are given in an array or balanced tree, the total running time is O((1/eps)logn+(1/eps2)log(1/eps))for rigid motions and O((1/eps)logn+(1/eps)log(1/eps)) for translations.

Hee-Kap Ahn, Otfried Cheong, Chong-Dae Park, Chan-Su Shin and Antoine Vigneron
In Proc. 21st Annu. ACM Symposium on Computational Geometry, 2005, and in Computational Geometry: Theory and Applications, 37(1):3-15, 2007


Stacking and Bundling two Convex Polygons

Given two compact convex sets C1 and C2 in the plane, we consider the problem of finding a placement deltaC1 of C1 that minimizes the area of the convex hull of the union of deltaC1 andC2. We first consider the case where deltaC1 and C2 are allowed to intersect (as in “stacking” two flat objects in a convex box), and then add the restriction that their interior has to remain disjoint (as when “bundling” two convex objects together into a tight bundle). In both cases, we consider both the case where we are allowed to reorient C1, and where the orientation is fixed. In the case without reorientations, we achieve exact near-linear time algorithms, in the case with reorientations we compute a (1+eps)-approximation in time O(eps(-1/2)logn+ eps(-3/2)logeps(-1/2)), if two sets are convex polygons with n vertices in total.

Hee-Kap Ahn, Otfried Cheong
In Proc. 16th Annual International Symposium on Algorithms and Computation, pages 40-49, 2005.


Maximum Overlap and Minimum Convex Hull of Two Convex Polyhedra under Translations

Given two convex polyhedra P and Q in three-dimensional space, we consider two related problems of shape matching: (1) finding a translation t1 in R3 of Q that maximizes the volume of their overlap of P and (Q+t1), and (2) finding a translation t2 in R3 that minimizes the volume of the convex hull of P U (Q+t2). For the maximum overlap problem, we observe that the d-th root of the objective function is concave and present an algorithm that computes the optimal translation in expected time O(n3log4n). This method generalizes to higher dimensions d>3 with expected running time O(nd+1 -3/d(logn)d+1). For the minimum convex hull problem, we show that the objective function is convex. The same method used for the maximum overlap problem can be applied to this problem and the optimal translation can be computed in the same time bound.Hee-Kap Ahn, Peter Brass and Chan-Su Shin
Computational Geometry: Theory and Applications, 40, pages 171-177, 2008

Maximum Overlap of Convex Polytope under Translation

Given two convex polytopes bounded by a total of n hyperplanes in Rd for some constant d >= 3, we compute the translation of one in order to maximize the volume of the intersection with the other polytope. Under some mild non-degeneracy assumptions, our algorithm runs inO(n|_d/2_|+1logd-1 n) time with probability at least 1-n-O(1). The running time can be improved toO(nlog3 n) in three dimensions.

Hee-Kap Ahn, Siu-Wing Cheng and Iris Reinbacher

Substituting a complex geometric shape by a “simpler” one is motivated by many applications. A typical example is the problem of computing the smallest (area) enclosing disc (or annulus, square, …) of a given set of points in d-dimensional Euclidean space. Unfortunately many of these problems turn out to be computationally difficult. Many of them are NP-hard, and for many others the best known solutions have polynomial runtimes of high degree which renders these algorithms uninteresting from a practical point of view. A possible solution is that instead of insisting on computing the exact solution for such an optimization problem, one looks for a solution that approximates the optimum reasonably well.


Inscribing an Axially Symmetric Polygon and other Approximation Algorithms for Planar Convex Sets

Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in C, and the smallest such set S’ that contains C. More precisely, for any eps>0, we find an axially symmetric convex polygon Q inscribed in C with area |Q|>(1-eps)|S| and we find an axially symmetric convex polygon Q’ containing C with area |Q’|<(1+eps)|S’|.

Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin and Antoine Vigneron
In Proc. 7th Annual International Computing and Combinatorics Conference, 2004, and in Computational Geometry: Theory and Applications, 33(3):152-164, 2006


Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle alpha(x, Q) of a point x not in Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q of C is the minimum aperture angle of any x in C \ Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q ofC with aperture angle approximation error (1 – 2/(k+1)) pi. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of kvertices of P) with Hausdorff distance sigma, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q ofP such that the Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).

Hee-Kap Ahn, Sang Won Bae, Otfried Cheong and Joachim Gudmundsson
In Proc. 23rd Annual ACM Symposium on Computational Geometry, pages 37-45, 2007. and to appear in Discrete & Computational Geometry.


Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations

Given a set of points in the plane, we consider the two non-convex enclosingshapes with the minimum area: the L-shape and the quadrant hull. This paper proposes efficient algorithms of computing each of two shapes enclosing given points with the minimum area over all orientations. The algorithms run in time quadratic in the number of given points by efficiently maintaining the set of extremal points.

Hee-Kap Ahn, Sang Won Bae, Chunseok Lee, Sunghee Choi and Kyung-Yong Chwa
In Proc. 18th Annual International Symposium on Algorithms and Computation, 2007.


Covering a Point Set by Two Disjoint Rectangles

Given a set S of n points in the plane, the disjoint two-rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the rectangles are free to rotate but must remain parallel to each other, and (2) one rectangle is axis-parallel but the other rectangle is allowed to be in arbitrary orientation. For both of the problems, we present O(n2log n)-time algorithms using O(n) space.

Hee-Kap Ahn and Sang Won Bae
In Proc. 19th Annual International Symposium on Algorithms and Computation, 2008.


워드프레스에 오신 것을 환영합니다. 이것은 첫번째 글입니다. 이 글을 고치거나 지운 후에 블로깅을 시작하세요!