Covering points by disjoint boxes with outliers
From MaRDI portal
Publication:617548
DOI10.1016/j.comgeo.2010.10.002zbMath1217.68109OpenAlexW2128262571MaRDI QIDQ617548
Martin L. Demaine, Hee-Kap Ahn, Matias Korman, Erik D. Demaine, Sang Won Bae, Sang-Sub Kim, Wanbin Son, Iris Reinbacher
Publication date: 21 January 2011
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.10.002
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)
Related Items
Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions ⋮ Computing a minimum-width square or rectangular annulus with outliers ⋮ Cause I'm a genial imprecise point: outlier detection for uncertain data ⋮ A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks ⋮ Matching colored points with rectangles ⋮ Computing a Minimum-Width Square or Rectangular Annulus with Outliers
Cites Work
- Unnamed Item
- Enclosing \(k\) points in the smallest axis parallel rectangle
- Covering a set of points by two axis-parallel boxes
- Covering a set of points in a plane using two parallel rectangles
- Algorithms for optimal outlier removal
- Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
- Optimal packing and covering in the plane are NP-complete
- Geometric applications of a randomized optimization technique
- Lower bounds for covering problems
- On geometric optimization with few violated constraints
- Discrete rectilinear 2-center problems
- Finding k points with minimum diameter and related problems
- On the Complexity of Some Common Geometric Location Problems
- Covering a Point Set by Two Disjoint Rectangles
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Planar Formulae and Their Uses
- A combinatorial bound for linear programming and related problems
- Low-Dimensional Linear Programming with Violations
