Optimizing squares covering a set of points
From MaRDI portal
Publication:1749537
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
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