Covering points by disjoint boxes with outliers

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

zbMATH Keywords

optimizationoutliersNP-hardrectangle coveringrectilinear \(p\)-center problemsquare covering

Mathematics Subject Classification ID

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