Smallest \(k\)-enclosing rectangle revisited
From MaRDI portal
Publication:2046452
DOI10.1007/s00454-020-00239-3OpenAlexW3081821159MaRDI QIDQ2046452
Sariel Har-Peled, Timothy M. Chan
Publication date: 18 August 2021
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.06785
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (2)
Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enclosing \(k\) points in the smallest axis parallel rectangle
- Necklaces, convolutions, and \(X+Y\)
- Relative \((p,\varepsilon )\)-approximations in geometry
- Two-dimensional range successor in optimal time and almost linear space
- Algorithms for optimal outlier removal
- Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
- A linear-time algorithm for a special case of disjoint set union
- Reporting points in halfspaces
- Approximate closest-point queries in high dimensions
- Approximate nearest neighbor queries revisited
- Iterated nearest neighbors and finding minimal polytopes
- Fast algorithms for computing the smallest \(k\)-enclosing circle
- Geometric applications of a randomized optimization technique
- Maximum-weight planar boxes in \(O(n^2)\) time (and better)
- Towards polynomial lower bounds for dynamic problems
- Clustered Integer 3SUM via Additive Combinatorics
- Finding k points with minimum diameter and related problems
- Online Sorted Range Reporting
- Efficiency of a Good But Not Linear Set Union Algorithm
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Tight Hardness Results for Maximum Weight Rectangles
- Static and Dynamic Algorithms for k-Point Clustering Problems
- On Problems Equivalent to (min,+)-Convolution
- Covering many points with a small-area box
- Faster all-pairs shortest paths via circuit complexity
This page was built for publication: Smallest \(k\)-enclosing rectangle revisited
