Covering with ellipses

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

doi:10.1007/s00453-003-1047-0

Covering with ellipses

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

Computer Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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.

Original language	English (US)
Pages (from-to)	145-160
Number of pages	16
Journal	Algorithmica (New York)
Volume	38
Issue number	1
DOIs	https://doi.org/10.1007/s00453-003-1047-0
State	Published - Oct 2003

Keywords

Algorithms and data structures
Approximation algorithm
Computational geometry
Proteomics
Set cover

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-003-1047-0

Cite this

@article{b2decc0af08b4265893dc45665262b1f,

title = "Covering with ellipses",

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, Approximation algorithm, Computational geometry, Proteomics, Set cover",

author = "Alon Efrat and Frank Hoffmann and Christian Knauer and Klaus Kriegel and G{\"u}nter Rote and Caola Wenk",

year = "2003",

month = oct,

doi = "10.1007/s00453-003-1047-0",

language = "English (US)",

volume = "38",

pages = "145--160",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Covering with ellipses

AU - Efrat, Alon

AU - Hoffmann, Frank

AU - Knauer, Christian

AU - Kriegel, Klaus

AU - Rote, Günter

AU - Wenk, Caola

PY - 2003/10

Y1 - 2003/10

N2 - 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.

AB - 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.

KW - Algorithms and data structures

KW - Approximation algorithm

KW - Computational geometry

KW - Proteomics

KW - Set cover

UR - http://www.scopus.com/inward/record.url?scp=21144435127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21144435127&partnerID=8YFLogxK

U2 - 10.1007/s00453-003-1047-0

DO - 10.1007/s00453-003-1047-0

M3 - Article

AN - SCOPUS:21144435127

SN - 0178-4617

VL - 38

SP - 145

EP - 160

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -

Covering with ellipses

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this