Schreiber Building
Computational Geometry Seminar
Wednesday, March 21st, 2007, 16:10-18:00
Room 309
Schreiber Building
We present an algorithm for computing a piecewise
linear approximation of a useful subset of the medial axis
of the complement of the union of three-dimensional balls.
We refer to this approximate subset as AMAT. The core idea
of the algorithm is to approximate the input balls using a
set K of balls of a fixed radius r, the radius of the
smallest ball in the input. This enables the extraction of
the medial-axis approximation from the alpha complex of K
for alpha=r. AMAT is composed of the dual Voronoi faces
of every simplex that is not in the alpha complex. We
define the Path-axis to be a subset of the medial axis
without 'dead ends', and show that AMAT approximates it.
Finally, we briefly present biological applications where
AMAT is used to find channels in geometric models of
proteins. The talk will be self contained and will start
with an overview of alpha shapes and the Lambda-medial
axis.