|
|||||
|
|
Covering with Ellipses |
|
| Authors: | Alon Efrat Frank Hoffmann Christian Knauer Klaus Kriegel Günter Rote Caola Wenk |
| Affiliation: | (1) Computer Science Department, Gould-Simpson 721, University of Arizona, 1040 E 4th St., Tucson, AZ 85721-0077, USA;(2) Institute of Computer Science, Freie Universität Berlin, Takustraße 9, D-14195 Berlin, Germany |
| Abstract: | 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. |
| Keywords: | Algorithms and data structures Computational geometry Approximation algorithm Setcover Proteomics |
| 本文献已被 SpringerLink 等数据库收录！ | |