Slice and dice: a simple, improved approximate tiling recipe

ABSTRACT

We are given a two dimensional array A[1 ⋅⋅⋅ 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 MIN-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.

REFERENCES

• 1: P. K. Agarwal , E. F. Grove , T. M. Murali , J. S. Vitter, Binary space partitions for fat rectangles, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.482, October 14-16, 1996
• 2: Pankaj K. Agarwal , Subhash Suri, Surface approximation and geometric partitions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.24-33, January 23-25, 1994, Arlington, Virginia, United States
• 3: C. Ballieux. Motion planning using binary space partitions. Technical Report, Utrecht University, 1993.
• 4: Berman Piotr , DasGupta Bhaskar , Muthukrishnan S., On the Exact Size of the Binary Space Partitioning of Sets of Isothetic Rectangles with Applications, Certer for Discrete Mathematics & Theoretical Computer Science, 2000
• 5: Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan , Suneeta Ramaswami, Improved approximation algorithms for rectangle tiling and packing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.427-436, January 07-09, 2001, Washington, D.C., United States
• 6: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 7: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.99-106, July 1989
• 8: Fabrizio d'Amore , Paolo Guilio Franciosa, On the optimal binary plane partition for sets of isothetic rectangles, Information Processing Letters, v.44 n.5, p.255-259, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90210-M]
• 9: Mark de Berg, Linear Size Binary Space Partitions for Fat Objects, Proceedings of the Third Annual European Symposium on Algorithms, p.252-263, September 25-27, 1995
• 10: Mark de Berg , Marko de Groot , Mark H. Overmars, New Results on Binary Space Partitions in the Plane (Extended Abstract), Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, p.61-72, July 06-08, 1994
• 11: Adrian Dumitrescu , Joseph S. G. Mitchell , Micha Sharir, Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles, Proceedings of the seventeenth annual symposium on Computational geometry, p.141-150, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378649]
• 12: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.124-133, July 1980
• 13: Viet Hai Nguyen , Peter Widmayer, Binary Space Partitions for Sets of Hyperrectangles, Proceedings of the 1995 Asian Computing Science Conference on Algorithms, Concurrency and Knowledge, p.59-72, December 11-13, 1995
• 14: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 15: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 16: H. V. Jagadish , Nick Koudas , S. Muthukrishnan, Mining Deviants in a Time Series Database, Proceedings of the 25th International Conference on Very Large Data Bases, p.102-113, September 07-10, 1999
• 17: Sanjeev Khanna , S. Muthukrishnan , Mike Paterson, On approximating rectangle tiling and packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 25-27, 1998, San Francisco, California, United States
• 18: Andrzej Lingas, The Power of Non-Rectilinear Holes, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.369-383, July 12-16, 1982
• 19: Krzysztof Lorys , Katarzyna Paluch, Rectangle tiling, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.206-213, September 05-08, 2000
• 20: F. Manne. Load Balancing in Parallel Sparse Matrix Computation. Ph.D. Thesis, Department of Informatics, University of Bergen, Norway, 1993.
• 21: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 22: Joseph S. B. Mitchell, On maximum flows in polyhedral domains, Journal of Computer and System Sciences, v.40 n.1, p.88-123, February 1990 [doi>10.1016/0022-0000(90)90020-L]
• 23: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 24: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceeding of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• 25: B. Naylor and W. Thibault. Application of BSP trees to ray-tracing and CSG evaluation. Technical Report GIT-ICS 86/03, Georgia Tech., Feb 1986.
• 26: T. Ohtsuki. Minimum Dissection of Rectilinear Polygons. Proc. IEEE Symp. on Circuits and Systems (1982), 1210-1213.
• 27: L. Pagli, E. Lodi, F. Luccio, C. Mugnai and W. Lipski. On Two Dimensional Data Organization 2. Fund. Inform., 2 (1979), 211-226.
• 28: Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
• 29: Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Journal of Algorithms, v.13 n.1, p.99-113, March 1992 [doi>10.1016/0196-6774(92)90007-Y]
• 30: C. H. Papadimtriou, personal communication.
• 31: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• 32: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 33: Jonathan P. Sharp, Tiling Multi-dimensional Arrays, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, p.500-511, August 30-September 03, 1999
• 34: Adam Smith , Subhash Suri, Rectangular tiling in multi-dimensional arrays, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.786-794, January 17-19, 1999, Baltimore, Maryland, United States
• 35: P. van Oosterom. A modified binary space partition for geographic information systems. Int. J. GIS, 4(2), 133-146, 1990.