A note on finding a maximum empty rectangle

DOI10.1016/0166-218X(86)90071-5MaRDI QIDQ1079570zbMATH OpenFDO

Authors Mikhail J. Atallah, Greg N. Frederickson

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(86)90071-5

zbMATH Keywords

maximum empty rectangle problem

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Review text

Given a rectangle A and a set S of n points in A, the maximum empty rectangle problem is that of finding a largest-area rectangle which is contained in A, has its sides parallel to those of A, and does not contain any of the points in S. This note describes an efficient algorithm for solving this problem.

Recommendations

• On the maximum empty rectangle problem
• A new algorithm for the largest empty rectangle problem
• scientific article; zbMATH DE number 3883624
• Largest empty rectangle among a point set
• Efficient algorithms for the largest rectangle problem

Cites work

• scientific article; zbMATH DE number 3883624 (Why is no real title available?)
• Maintenance of configurations in the plane
• On the maximum empty rectangle problem

Cited in

(21)

• An efficient algorithm for maxdominance, with applications
• Efficient algorithms for the largest rectangle problem
• Mining for empty spaces in large data sets.
• On the number of maximum empty boxes amidst \(n\) points
• On the largest empty axis-parallel box amidst \(n\) points
• Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
• Fast sequential and parallel algorithms for finding the largest rectangle separating two sets
• scientific article; zbMATH DE number 3883624 (Why is no real title available?)
• scientific article; zbMATH DE number 4033105 (Why is no real title available?)
• Largest empty rectangle among a point set
• scientific article; zbMATH DE number 2080472 (Why is no real title available?)
• On Computing a Largest Empty Arbitrarily Oriented Rectangle
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• A new algorithm for the largest empty rectangle problem
• Maximal empty boxes amidst random points
• An efficient algorithm for computing the maximum empty rectangle in three dimensions
• Fast parallel algorithms for the maximum empty rectangle problem.
• Parametric algorithm to find the largest empty rectangle from a set of line segments
• On the maximum empty rectangle problem
• Fast algorithms for finding disjoint subsequences with extremal densities
• Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions

This page was built for publication: A note on finding a maximum empty rectangle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079570)