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 *P*and *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 *C _{1}* and

*C*in the plane, we consider the problem of finding a placement

_{2}*deltaC*of

_{1}*C*that minimizes the area of the convex hull of the union of

_{1}*deltaC*and

_{1}*C*. We first consider the case where

_{2}*deltaC*and

_{1}*C*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

_{2}*C*, 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}*(1+eps)*-approximation in time

*O(eps*, if two sets are convex polygons with n vertices in total.

^{(-1/2)}logn+ eps^{(-3/2)}logeps^{(-1/2)})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 *t _{1} in R^{3}* of

*Q*that maximizes the volume of their overlap of

*P*and

*(Q+t*, and (2) finding a translation

_{1})*t*that minimizes the volume of the convex hull of

_{2}in R^{3}*P U (Q+t*. For the maximum overlap problem, we observe that the

_{2})*d*-th root of the objective function is concave and present an algorithm that computes the optimal translation in expected time

*O(n*. This method generalizes to higher dimensions

^{3}log^{4}n)*d>3*with expected running time

*O(n*. 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

^{d+1 -3/d}(logn)^{d+1})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 *R ^{d}* 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 in

*O(n*time with probability at least

^{|_d/2_|+1}log^{d-1}n)*1-n*. The running time can be improved to

^{-O(1)}*O(nlog*in three dimensions.

^{3}n)Hee-Kap Ahn, Siu-Wing Cheng and Iris Reinbacher