| Article ID: | iaor201113544 |
| Volume: | 38 |
| Issue: | 1 |
| Start Page Number: | 145 |
| End Page Number: | 160 |
| Publication Date: | Jan 2004 |
| Journal: | Algorithmica |
| Authors: | Rote Gnter, Knauer Christian, Efrat Alon, Hoffmann Frank, Kriegel Klaus, Wenk Caola |
| Keywords: | biology |
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.