Smallest k-enclosing rectangle revisited

DOI10.4230/LIPICS.SOCG.2019.23MaRDI QIDQ5088950zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Sariel Har-Peled

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2019.23

zbMATH Keywords

outliersapproximation algorithmsgeometric optimizationconditional lower bounds

Mathematics Subject Classification ID

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

Recommendations

• Smallest \(k\)-enclosing rectangle revisited
• Enclosing k points in the smallest axis parallel rectangle
• Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
• Covering many points with a small-area box
• Computing the smallest \(k\)-enclosing circle and related problems

Cites work

• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Algorithms for optimal outlier removal
• Approximate closest-point queries in high dimensions
• Approximate nearest neighbor queries revisited
• Clustered Integer 3SUM via Additive Combinatorics
• Covering many points with a small-area box
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Efficiency of a Good But Not Linear Set Union Algorithm
• Enclosing k points in the smallest axis parallel rectangle
• Fast algorithms for computing the smallest \(k\)-enclosing circle
• Faster all-pairs shortest paths via circuit complexity
• Finding k points with minimum diameter and related problems
• Geometric applications of a randomized optimization technique
• Iterated nearest neighbors and finding minimal polytopes
• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• Necklaces, convolutions, and \(X+Y\)
• On Problems Equivalent to (min,+)-Convolution
• Range selection and median: tight cell probe lower bounds and adaptive data structures
• Relative (p, )-approximations in geometry
• Reporting points in halfspaces
• Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Tight hardness results for maximum weight rectangles
• Towards polynomial lower bounds for dynamic problems

Cited in

(3)

• Smallest \(k\)-enclosing rectangle revisited
• White Noise Test from Ordinal Patterns in the Entropy–Complexity Plane
• Small-size ε-nets for axis-parallel rectangles and boxes

This page was built for publication: Smallest k-enclosing rectangle revisited

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