Covering Shapes by Ellipses for the Computer Analysis of Protein Patterns

Frank Hoffmann
Klaus Kriegel
Christof Schultz
Institut für Informatik
Freie Universität Berlin

Alon Efrat
Computer Science Department
Stanford University
email: alon@Graphics.Stanford.EDU

Report B-00-11
July 2000

We study the problem of how to cover a polygonal region by a small number of axis--parallel ellipses. This question is well motivated by a special pattern recognition task where one has to identify ellipse shaped protein spots in 2-dimensional electrophoresis images. We present and discuss two algorithmic approaches solving this problem: a greedy brute force method and a linear programming formulation. Furthermore we discuss related theoretical questions.
Get the report here or by anonymous ftp:
File:   pub/reports/