On the maximum empty rectangle problem |
| |
| Authors: | A Naamad DT Lee W-L Hsu |
| |
| Institution: | Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60201, USA;Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60201, USA |
| |
| Abstract: | Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n2) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)2) expected time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
