Faster algorithms for largest empty rectangles and boxes

DOI10.4230/LIPICS.SOCG.2021.24MaRDI QIDQ7234080zbMATH OpenFDO

Authors Timothy M. Chan

Publication date 27 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2021.24

zbMATH Keywords

Klee's measure problemlargest empty boxlargest empty rectangle

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A (slightly) faster algorithm for Klee's measure problem
• A unifying look at data structures
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• An improved algorithm for Klee's measure problem on fat boxes
• An optimal algorithm with unknown time complexity for convex matrix searching
• An optimal minimum spanning tree algorithm
• An upper bound on the minimal dispersion
• Applications of generalized matrix searching to geometric algorithms
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• Computational geometry. Algorithms and applications.
• Computing the Largest Empty Rectangle
• Finding the largest area axis-parallel rectangle in a polygon
• Geometric applications of a randomized optimization technique
• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 7788426 (Why is no real title available?)
• Klee's measure problem made easy
• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• New Upper Bounds in Klee’s Measure Problem
• On constant factors in comparison-based geometric algorithms and data structures
• On the largest empty axis-parallel box amidst \(n\) points
• On the maximum empty rectangle problem
• On the number of maximum empty boxes amidst \(n\) points
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• Two approaches to building time-windowed geometric data structures
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions

This page was built for publication: Faster algorithms for largest empty rectangles and boxes

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