Porschen, Stefan
(2007).
On rectangular covering problems.
Working Paper.
|
PDF
zaik2007-533.pdf Download (310kB) | Preview |
Abstract
Many applications like picture processing, data compression or pattern recognition require a covering of a set of points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic programming algorithms for covering point sets by regular rectangles, that have to obey certain (parameterized) boundary conditions. The concrete representative out of a class of objective functions that is studied is to minimize sum of area, circumference and number of patches used. This objective function may be motivated by requirements of numerically solving PDE's by discretization over (adaptive multi-)grids. More precisely, we propose exact deterministic algorithms for such problems based on a (set theoretic) dynamic programming approach yielding a time bound of O(n^23^n) . In a second step this bound is (asymptotically) decreased to O(n^62^n) by exploiting the underlying rectangular and lattice structures. Finally, a generalization of the problem and its solution methods is discussed for the case of arbitrary (finite) space dimension.
| Item Type: | Preprints, Working Papers or Reports (Working Paper) | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-549078 | ||||||||
| Date: | 2007 | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | No | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54907 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |