Optimizing squares covering a set of points

DOI10.1016/j.tcs.2015.11.029zbMath1390.68707OpenAlexW2206314130MaRDI QIDQ1749537

Tsunehiko Kameda, Sergey Bereg, Priya Ranjan Sinha Mahapatra, Zhao Song, Sandip Das, Binay K. 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)

Related Items

Discrete and mixed two-center problems for line segments, Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares, Covering uncertain points in a tree, Covering a set of line segments with a few squares, Covering a set of line segments with a few squares

Cites Work

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