Smallest \(k\)-enclosing rectangle revisited
type: Item
instance of: scholarly article
title: Smallest \(k\)-enclosing rectangle revisited
author: Timothy M. Chan
author: Sariel Har-Peled
published in: Discrete \& Computational Geometry
publication date: 2021-08-18T00:00:00Z
full work available at URL: https://arxiv.org/abs/1903.06785
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 7382964
zbMATH Keywords: geometric optimization
zbMATH Keywords: outliers
zbMATH Keywords: approximation algorithms
zbMATH Keywords: conditional lower bounds
MaRDI profile type: Publication
OpenAlex ID: W3081821159
cites work: Finding k points with minimum diameter and related problems
cites work: Algorithms for optimal outlier removal
cites work: Tight Hardness Results for Maximum Weight Rectangles
cites work: Maximum-weight planar boxes in \(O(n^2)\) time (and better)
cites work: Covering many points with a small-area box
cites work: Approximate closest-point queries in high dimensions
cites work: Necklaces, convolutions, and \(X+Y\)
cites work: Online Sorted Range Reporting
cites work: Approximate nearest neighbor queries revisited
cites work: Geometric applications of a randomized optimization technique
cites work: Clustered Integer 3SUM via Additive Combinatorics
cites work: Q5417615
cites work: Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
cites work: On Problems Equivalent to (min,+)-Convolution
cites work: Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
cites work: Static and Dynamic Algorithms for k-Point Clustering Problems
cites work: Iterated nearest neighbors and finding minimal polytopes
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Fast algorithms for computing the smallest \(k\)-enclosing circle
cites work: Relative \((p,\varepsilon )\)-approximations in geometry
cites work: Q5365082
cites work: Q5111741
cites work: Reporting points in halfspaces
cites work: Towards polynomial lower bounds for dynamic problems
cites work: Enclosing \(k\) points in the smallest axis parallel rectangle
cites work: Efficiency of a Good But Not Linear Set Union Algorithm
cites work: Faster all-pairs shortest paths via circuit complexity
cites work: Two-dimensional range successor in optimal time and almost linear space
DOI: 10.1007/S00454-020-00239-3
Recommended article: Smallest k-enclosing rectangle revisited
Recommended article: Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
Recommended article: Enclosing \(k\) points in the smallest axis parallel rectangle
Recommended article: Computing the smallest \(k\)-enclosing circle and related problems
Recommended article: Computing the smallest k-enclosing circle and related problems
Recommended article: Q3540322
Recommended article: Minimum K-Adjacent Rectangles of Orthogonal Polygons and its Application
Recommended article: Close approximations of minimum rectangular coverings
Recommended article: The Rectangle Enclosure and Point-Dominance Problems Revisited
Recommended article: Q5420025
description: scientific article; zbMATH DE number 7382964