[Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 2001,08]
Algorithms and data structures, Computational geometry, Approximation algorithm, Set cover, Proteomics
004 Data processing and Computer science 510 Mathematics
We address the problem of how to cover a set of "required points" by a small number of "axis-parallel ellipses" that avoid a second set of "forbidden points". We study geometric properties of such covers and present an efficient randomized approximation algorithm for the cover construction. This question is motivated by a special pattern recognition task where one has to identify ellipse-shaped protein spots in two-dimensional electrophoresis images.
If your browser can't open the file, please download the file first and then open it