Covering with Ellipses

Alon Efrat
University of Arizona, Computer Science Department,
Gould-Simpson 721, P.O. Box 210077, Tucson, Arizona, U.S.A.
email: alon@CS.Arizona.EDU

Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: name@inf.fu-berlin.de

Abstract
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.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-01-08.ps.gz