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( n 2 ) 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. |
Year | DOI | Venue |
---|---|---|
1984 | 10.1016/0166-218X(84)90124-0 | DISCRETE APPLIED MATHEMATICS |
Field | DocType | Volume |
Binary logarithm,Discrete mathematics,Combinatorics,Largest empty rectangle,Rectangle,Mathematics,Rectangle method | Journal | 8 |
Issue | ISSN | Citations |
3 | 0166-218X | 65 |
PageRank | References | Authors |
8.41 | 2 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amnon Naamad | 1 | 1019 | 181.64 |
D.T. Lee | 2 | 627 | 78.14 |
W.-L Hsu | 3 | 65 | 8.41 |