A new algorithm for the largest empty rectangle problem

DOI10.1007/BF01840377zbMath0689.68065MaRDI QIDQ582097

Jianyong Qiao, Sumit K. Garg

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

computational complexity; computational geometry; largest empty rectangle problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U99: Computing methodologies and applications

Related Items

On Computing a Largest Empty Arbitrarily Oriented Rectangle, An efficient algorithm for computing the maximum empty rectangle in three dimensions, Fast parallel algorithms for the maximum empty rectangle problem., Maximal Empty Boxes Amidst Random Points, Fast algorithms for finding disjoint subsequences with extremal densities, An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation, An efficient algorithm for maxdominance, with applications, An optimal algorithm for rectangle placement, Mining for empty spaces in large data sets., Maximal empty coboids among points and blocks, A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids, 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, Polynomial Time Algorithms for Bichromatic Problems, Maximal strips data structure to represent free space on partially reconfigurable FPGAs

Cites Work

• On the maximum empty rectangle problem
• A note on finding a maximum empty rectangle
• Computing the Largest Empty Rectangle