Covering points by disjoint boxes with outliers

DOI10.1016/j.comgeo.2010.10.002zbMath1217.68109MaRDI 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

optimization; outliers; NP-hard; rectangle covering; rectilinear \(p\)-center problem; square covering

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

52B55: Computational aspects related to convexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

52C22: Tilings in (n) dimensions (aspects of discrete geometry)

Related Items

Matching colored points with rectangles, 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, A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks, 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