A new algorithm for the largest empty rectangle problem |
| |
| Authors: | M Orlowski |
| |
| Affiliation: | (1) Council for Scientific and Industrial Research, National Research Institute for Mathematical Sciences, P.O. Box 395, 0001 Pretoria, Republic of South Africa;(2) Present address: Department of Computing, Brisbane College of Advanced Education, 4031 Kedron, Queensland, Australia |
| |
| Abstract: | A rectangleA and a setS ofn points inA 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 inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn). |
| |
| Keywords: | Computational geometry Algorithms Computational complexity Largest empty rectangle problem |
| 本文献已被 SpringerLink 等数据库收录！ |
|
