A new algorithm for the largest empty rectangle problem. (English) Zbl 0689.68065
Summary: A rectangle A and a set S of n points in A are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained in A and not containing any point of S in its interior. The computational complexity of the presented algorithm is O(n log n\(+s)\), where s is the number of possible restricted rectangles considered. Moreover, the expected performance is O(n\(\cdot \log n)\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68U99 | Computing methodologies and applications |
References:
| [1] | Atallah, M. J.; Frederickson, G. N., A note on finding a maximum empty rectangle, Discrete Applied Mathematics, 13, 87-91 (1986) · Zbl 0598.05018 · doi:10.1016/0166-218X(86)90071-5 |
| [2] | Chazelle, B.; Drysdale, R. F.; Lee, D. T., Computing the largest empty rectangle, SIAM Journal of Computing, 15, 300-315 (1986) · Zbl 0608.68059 · doi:10.1137/0215022 |
| [3] | Namaad, A.; Hsu, W. L.; Lee, D. T., On the maximum empty rectangle problem, Applied Discrete Mathematics, 8, 267-277 (1984) · Zbl 0543.68057 · doi:10.1016/0166-218X(84)90124-0 |
| [4] | Toussaint, G. T.; Avis, D., On a convex hull algorithm for polygons and its applications to triangulation problems, Pattern Recognition, 15, 23-29 (1982) · doi:10.1016/0031-3203(82)90057-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
