Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares

DOI10.1016/j.tcs.2018.10.013zbMath1435.68353arXiv1709.04870OpenAlexW2963246055MaRDI QIDQ1737597

Subhas C. Nandy, Sanjib Sadhu, Sasanka Roy, Suchismita Roy

Publication date: 23 April 2019

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

Full work available at URL: https://arxiv.org/abs/1709.04870

zbMATH Keywords

computational geometrytwo-center problemcovering line segments by squareshitting line segments by squarestwo-pass algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (5)

Discrete and mixed two-center problems for line segments ⋮ Corrigendum to: ``Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares ⋮ Covering a set of line segments with a few squares ⋮ Covering a set of line segments with a few squares ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Cites Work

• Unnamed Item
• Unnamed Item
• Base station placement on boundary of a convex polygon
• Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
• A faster algorithm for the two-center decision problem
• Minimum-perimeter enclosures
• A near-linear algorithm for the planar 2-center problem
• Approximation of convex figures by pairs of rectangles
• Optimizing squares covering a set of points
• Minimum area circumscribing polygons
• More planar two-center algorithms
• Discrete rectilinear 2-center problems
• An approximation algorithm for \(k\)-center problem on a convex polygon
• Simple \(O(n \log^{2} n)\) algorithms for the planar 2-center problem
• A simple linear algorithm for computing rectilinear 3-centers
• COVERING A POINT SET BY TWO DISJOINT RECTANGLES
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• An optimal algorithm for finding minimal enclosing triangles
• On the rectangularp-center problem
• Enclosing many boxes by an optimal pair of boxes
• Discrete and Computational Geometry

This page was built for publication: Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares