Optimizing squares covering a set of points

DOI10.1016/J.TCS.2015.11.029MaRDI QIDQ1749537zbMATH OpenOpenAlexFDO

Authors Sergey Bereg, Sandip Das, Tsunehiko Kameda, Priya Ranjan Sinha Mahapatra, Zhao Song, Binay Bhattacharya

Publication date 17 May 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.11.029

zbMATH Keywords

facility location\(k\)-center problempoint covering by squares

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Recommendations

• Optimizing squares covering a set of points
• Constrained square-center problems
• Square and Rectangle Covering with Outliers
• Discrete rectilinear 2-center problems
• Placing two axis-parallel squares to maximize the number of enclosed points

Cites work

• scientific article; zbMATH DE number 177557 (Why is no real title available?)
• scientific article; zbMATH DE number 1254001 (Why is no real title available?)
• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• A subexponential bound for linear programming
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• An optimal algorithm for finding minimal enclosing triangles
• Constrained minimum enclosing circle with center on a query line segment
• Covering a point set by two disjoint rectangles
• Covering a set of points in a plane using two parallel rectangles
• Covering point sets with two disjoint disks or squares
• Discrete rectilinear 2-center problems
• Finding kth paths and p-centers by generating and searching good data structures
• Finding minimal enclosing boxes
• Finding the smallest triangles containing a given convex polygon
• Fitting a step function to a point set
• Generalized Selection and Ranking: Sorted Matrices
• Line-constrained \(k\)-median, \(k\)-means, and \(k\)-center problems in the plane
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Lower bounds for covering problems
• New Upper Bounds in Klee’s Measure Problem
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On a circle placement problem
• On piercing sets of axis-parallel rectangles and rings
• On-line construction of the convex hull of a simple polyline
• Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• The number of guillotine partitions in d dimensions
• Time bounds for selection

Cited in

(9)

• Covering a set of line segments with a few squares
• Optimizing squares covering a set of points
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• Constrained square-center problems
• Placing two axis-parallel squares to maximize the number of enclosed points
• Square and Rectangle Covering with Outliers
• Optimal covering points and related problems
• Covering a set of line segments with a few squares
• Discrete and mixed two-center problems for line segments

This page was built for publication: Optimizing squares covering a set of points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749537)