Maximizing the overlap of two planar convex sets under rigid motions

다국어 초록 (Multilingual Abstract)

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