Abstract
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
ɛ
>
0
, we find an axially symmetric convex polygon
Q
⊂
C
with area
|
Q
|
>
(
1
−
ɛ
)
|
S
|
and we find an axially symmetric convex polygon
Q
′
containing
C with area
|
Q
′
|
<
(
1
+
ɛ
)
|
S
′
|
. We assume that
C is given in a data structure that allows to answer the following two types of query in time
T
C
: given a direction
u, find an extreme point of
C in direction
u, and given a line
ℓ, find
C
∩
ℓ
. For instance, if
C is a convex
n-gon and its vertices are given in a sorted array, then
T
C
=
O
(
log
n
)
. Then we can find
Q and
Q
′
in time
O
(
ɛ
−
1
/
2
T
C
+
ɛ
−
3
/
2
)
. Using these techniques, we can also find approximations to the perimeter, area, diameter, width, smallest enclosing rectangle and smallest enclosing circle of
C in time
O
(
ɛ
−
1
/
2
T
C
)
.