Smallest k-enclosing rectangle revisited

DOI10.4230/LIPICS.SOCG.2019.23OpenAlexW2920804372MaRDI QIDQ5088950FDOQ5088950

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

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

zbMATH Keywords

outliersapproximation algorithmsgeometric optimizationconditional lower bounds

Mathematics Subject Classification ID

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

Cites Work

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

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)