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 pattern recognition task where one has to identify ellipse-shaped protein spots in two-dimensional electrophoresis images.
Last update: August 15, 2017.