# Research

Shape Approximation

## 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*of

*C*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

*k*vertices 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*of

*P*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 enclosing shapes 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(n*-time algorithms using

^{2}log n)*O(n)*space.

Hee-Kap Ahn and Sang Won Bae

In Proc. 19th Annual International Symposium on Algorithms and
Computation, 2008.