Minkowski Sum and Medial Axis Transform

transform. Both of them are important tools in wide range of
applications. The focus will mainly be on the works of the speaker in
these topics.

The Minkovski sum of two sets $A$ and $B$ in $\mathbb{R}^2$ is
defined to be the set $\{ a + b \,|\, a \in A, b \in B \}$. Compared
to the simplicity of its definition, the geometry and topology of the
Minkovski sum of two planar domains has features quite complicated
even if the summands are relatively simple. For example, the Minkovski
sum of two simply connected planar domains need not be simply
connected. We define the notion of {\em semi-convexity} on planar
domains which extends the notion of convexity, and show that, in some
sense, it is the weakest possible condition on the planar domains for
the Minkovski sums of them to be homeomorphic to the unit disk.

The {\em medial axis transform} MAT($\Omega$) of a plane domain
$\Omega$ is the set of all pairs $(p,r)$ in $\mathbb{R}^2 \times
\mathbb{R}$ such that $B_r(p)$ is a maximal ball contained in
$\Omega$. The {\em medial axis} MA($\Omega$) of $\Omega$ is the set of
all points $p$ in $\mathbb{R}^2$ such that $(p,r) \in MAT(\Omega)$ for
some $r$. Medial axis is also called {\em skeleton}, {\em symmetric
axis}, {\it etc.} in the literature. We will talk about three aspects
of medial axis transform: shape, algorithm and instability. From some
assumptions on $\Omega$ which is in fact optimal in a sense, we show
that MA($\Omega$) and MAT($\Omega$) have {\em finite graph
structures}. By using the domain decomposition principle, we present
an efficient approximate algorithm for domains with free-form
boundary. One of the drawbacks of medial axis transform is its
instability under the boundary perturbation; It is unstable under the
standard metrics such as Hausdorff distance. We show that MAT of an
{\em injective domain} is stable under {\em relative Hausdorff
distance}. In fact, we obtain an upper bound of the relative Hausdorff
distance of the MAT of an injective domain, with respect to the MAT of
an arbitrary domain which is in small Hausdorff distance from the
original injective domain.