Computational Geometry Seminar

Wednesday, March 21st, 2007, 16:10-18:00

Room 309
Schreiber Building

Efficient Identification of Pathways in the Complement of the Union of Balls in R^3

Eitan Yaffe, Tel Aviv University


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.