Mathematics
and Computer Science Speaker Series
California State University, Stanislaus
Date: Friday, April 11, 2008
Time: 4:00 - 5:00 p.m
Room: P102
Speaker: John
Sarraille
Title: Minimal Coverings, Problems and Applications
Abstract: Consider the question of how to efficiently
construct a minimal or approximately minimal cover of a finite set of
points in a
Euclidean space using closed balls of a given diameter. This
comes up in facility-location problems and in the estimation of
fractal dimension. For embedding dimension 2 or more the minimal
covering problem is NP-hard, and so there is no known
polynomial-time algorithm. A brute force solution will be
described, special methods, heuristics, and a polynomial
approximation scheme. There will be speculation on how the ideas
presented might be exploited to improve techniques for
estimating fractal dimension.