Covering with ellipses
Efrat, Alon ;  Hoffmann, Frank ;  Knauer, Christian ;  Kriegel, Klaus ;  Rote, Günter ;  Wenk, Carola ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleCovering with ellipses
AuthorEfrat, Alon
AuthorHoffmann, Frank
AuthorKnauer, Christian
AuthorKriegel, Klaus
AuthorRote, Günter
AuthorWenk, Carola
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages12 S.
Series [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 2001,08]
KeywordsAlgorithms and data structures, Computational geometry, Approximation algorithm, Set cover, Proteomics
Classification (DDC)004 Data processing and Computer science
510 Mathematics
AbstractWe 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.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2001
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-10-29 : 12:52:14
Last changed2015-03-06 : 10:33:10
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004104