Covering with ellipses

Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Caola Wenk

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)145-160
Number of pages16
JournalAlgorithmica (New York)
Issue number1
StatePublished - Oct 2003


  • Algorithms and data structures
  • Approximation algorithm
  • Computational geometry
  • Proteomics
  • Set cover

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Covering with ellipses'. Together they form a unique fingerprint.

Cite this