Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, and Carola Wenk:

1. Covering shapes by ellipses

In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, January 2002, pp. 453–454. doi:10.1145/545381.545441

2. Covering with ellipses

Algorithmica 38 (2003), 145–160. doi:10.1007/s00453-003-1047-0


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.

  free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.