Faster algorithms for largest empty rectangles and boxes

DOI10.1007/s00454-022-00473-xarXiv2103.08043OpenAlexW3138822026MaRDI QIDQ6174805

Timothy M. Chan

Publication date: 17 August 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.08043

zbMATH Keywords

Klee's measure problemlargest empty rectanglelargest empty box

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

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

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