## 15. ÖMG-Kongress

Jahrestagung der Deutschen Mathematikervereinigung

#### 16. bis 22. September 2001 in Wien

**Sektion 3 - Diskrete Mathematik, Algorithmen**

Dienstag, 18. September 2001, 18.00, Hörsaal 23

**On Covering -Grid Points by Rectangles**
**Stefan Porschen**, **Universität Köln**

A problem of combinatorial geometry is
discussed: Cover a finite set of points lying on an integer grid
in the Euclidean plane by regular rectangles
such that the total area, circumference and number of rectangles used is
minimized. This problem seems to be NP-hard,
which is surely the case for related problems concerning covering
points arbitrarily distributed in the plane. Treating the case of
minimal rectangle side lengths
(grid constant), we propose an exact deterministic algorithm based on
set theoretic dynamic programming, which then is improved by exploiting
the rectangular and underlying grid structure. We also discuss a variant given by a
further parameter bounding the maximal possible covering
cardinality. For this, we are able to find a time bound by a polynomial of
degree . Generalizations to arbitrary
values of and arbitrary (finite) space dimensions are possible. (A
version of this talk has been presented at the
Cologne-Twente-Workshop 2001, an extended abstract of which may be
found as Electronic Notes on Discrete Mathematics (ENDM, Elsevier, Vol.8, 2001).)

Zeitplan der Sektion
Tagesübersicht
Liste der Vortragenden