Abstract
The maximum empty rectangle problem is as follows: Given a set of red points in ℝd and an axis-aligned hyperrectangle B, find an axis-aligned hyperrectangle R of greatest volume that is contained in B and contains no red points. In addition to this problem, we also consider three natural variants: where we find a hypercube instead of a hyperrectangle, where we try to contain as many blue points as possible instead of maximising volume, and where we do both. Combining the results of this paper with previous results, we now know that all four of these problems (a) are NP-complete if d is part of the input, (b) have polynomial-time sweep-plane solutions for any fixed d ≥ 3, and (c) have near linear time solutions in two dimensions.
This research is supported by the Natural Sciences and Engineering Research Council (NSERC).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Naamad, A., Lee, D., Hsu, W.: Maximum empty rectangle problem. Discrete Appl. Math. 8(3), 267–277 (1984)
Chazelle, B., Drysdale, R., Lee, D.: Computing the largest empty rectangle. SIAM J. Comput. 15, 300 (1986)
Aggarwal, A., Suri, S.: Fast algorithms for computing the largest empty rectangle. In: Symposium on Computational Geometry, pp. 278–290 (1987)
Nandy, S., Bhattacharya, B.: Maximal empty cuboids among points and blocks. Computers and Mathematics with Applications 36(3), 11–20 (1998)
Orlowski, M.: A new algorithm for the largest empty rectangle problem. Algorithmica 5(1), 65–73 (1990)
Datta, A., Soundaralakshmi, S.: An efficient algorithm for computing the maximum empty rectangle in three dimensions. Inform. Sciences 128(1-2), 43–65 (2000)
Eckstein, J., Hammer, P., Liu, Y., Nediak, M., Simeone, B.: The maximum box problem and its application to data analysis. Comput. Optim. Appl. 23(3), 285–298 (2002)
Aronov, B., Har-Peled, S.: On Approximating the Depth and Related Problems. SIAM J. Comput. 38(3), 899–921 (2008)
Liu, Y., Nediak, M.: Planar case of the maximum box and related problems. In: CCCG, pp. 14–18 (2003)
Edmonds, J., Gryz, J., Liang, D., Miller, R.J.: Mining for empty spaces in large data sets. Theor. Comput. Sci. 296(3), 435–452 (2003)
Dobkin, D., Gunopulos, D., Maass, W.: Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning. J. Comput. Syst. Sci. 52(3), 453–470 (1996)
Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: Sorted matrices. SIAM J. Comput. 13(1), 14–30 (1984)
Overmars, M., Yap, C.: New upper bounds in Klee’s measure problem. SIAM J. Comput. 20(6), 1034–1045 (1991)
Boissonnat, J.D., Sharir, M., Tagansky, B., Yvinec, M.: Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete & Computational Geometry 19(4), 485–519 (1998)
Kaplan, H., Rubin, N., Sharir, M., Verbin, E.: Counting colors in boxes. In: Bansal, N., Pruhs, K., Stein, C. (eds.) SODA, pp. 785–794. SIAM, Philadelphia (2007)
Lee, D.T., Wong, C.K.: Voronoi diagrams in l 1 (l ∞ ) metrics with 2-dimensional storage applications. SIAM J. Comput. 9(1), 200–211 (1980)
Aggarwal, A., Klawe, M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(1), 195–208 (1987)
McKenna, M., O’Rourke, J., Suri, S.: Finding the largest rectangle in an orthogonal polygon. In: Allerton Conference, pp. 486–495 (1985)
Dumitrescu, A., Jiang, M.: On the largest empty axis-parallel box amidst n points. arxiv.org reference arXiv:0909.3127 (2009) Submitted for publication
Agarwal, P.K., Kaplan, H., Sharir, M.: Computing the volume of the union of cubes. In: Erickson, J. (ed.) Symposium on Computational Geometry, pp. 294–301. ACM, New York (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Backer, J., Keil, J.M. (2010). The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)