# Slice and dice: A simple, improved approximate tiling recipe

Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

We are given a two dimensional array A[l ... n, 1 ... n] where each A[i,j] stores a non-negative number. A (rectangular) tiling of A is a collection of rectangular portions A[l...r,t...b], called tiles, such that no two tiles overlap and each entry A[i, j] is contained in a tile. The weight of a tile is the sum of all array entries in it. In the MAX-MIN problem, we are given a weight bound W and our goal is to find a tiling such that (a) each tile is of weight at least W (the MIN condition) and (b) the number of tiles is maximized (the MAX condition). In the HIN-MAX problem, we are given a weight bound W again and our goal is to find a tiling such that (a) each tile has weight at most W and (b) the number of tiles is minimized. These two basic problems have many variations depending on the weight functions, whether some areas of A must not be covered, or whether some portion of A may be discarded, etc. These problems are not only natural combinatorial problems, but also arise in a plethora of applications, e.g., in databases and data mining, video compression, load balancing, building index structures, manufacturing and so forth. Both the above tiling problems (as well as all of their variations relevant to this paper) are known to be NP-hard. In this paper, we present approximations algorithms for solving these problems based on epicurean methods : variations of a basic slice-and-dice technique. Surprisingly, these simple algorithms yield small constant factor approximations for all these problems. For some of the problems, our results are the first known approximations; for others, our results improve the known algorithms significantly in approximation bounds and/or running time. Of independent interest are the tight bounds we show for sizes of the binary space partition trees for isothetic rectangles.

Original language English (US) Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 Association for Computing Machinery 455-464 10 089871513X Published - 2002 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United StatesDuration: Jan 6 2002 → Jan 8 2002

### Publication series

Name Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 06-08-January-2002

### Other

Other 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 United States San Francisco 1/6/02 → 1/8/02

## ASJC Scopus subject areas

• Software
• Mathematics(all)

## Fingerprint

Dive into the research topics of 'Slice and dice: A simple, improved approximate tiling recipe'. Together they form a unique fingerprint.