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

DOI10.1016/J.TCS.2018.10.013MaRDI QIDQ1737597zbMATH OpenOpenAlexFDO

Authors Sanjib Sadhu, Sasanka Roy, Subhas C. Nandy, 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)

Abstract: This paper discusses the problem of covering and hitting a set of line segments $calL$ in ${mathbbR}^2$ by a pair of axis-parallel squares such that the side length of the larger of the two squares is minimized. We also discuss the restricted version of covering, where each line segment in $calL$ is to be covered completely by at least one square. The proposed algorithm for the covering problem reports the optimum result by executing only two passes of reading the input data sequentially. The algorithm proposed for the hitting and restricted covering problems produces optimum result in $O(n)$ time. All the proposed algorithms are in-place, and they use only $O(1)$ extra space. The solution of these problems also give a $sqrt2$ approximation for covering and hitting those line segments $calL$ by two congruent disks of minimum radius with same computational complexity.

Recommendations

• Optimal covering and hitting of line segments by two axis-parallel squares
• Line segment disk cover
• Corrigendum to: ``Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares

Cites work

• scientific article; zbMATH DE number 1696646 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• A faster algorithm for the two-center decision problem
• A near-linear algorithm for the planar 2-center problem
• A simple linear algorithm for computing rectilinear 3-centers
• An approximation algorithm for \(k\)-center problem on a convex polygon
• An optimal algorithm for finding minimal enclosing triangles
• Approximation of convex figures by pairs of rectangles
• Base station placement on boundary of a convex polygon
• Covering a point set by two disjoint rectangles
• Discrete rectilinear 2-center problems
• Enclosing many boxes by an optimal pair of boxes
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Minimum area circumscribing polygons
• Minimum-perimeter enclosures
• More planar two-center algorithms
• On the minimum perimeter triangle enclosing a convex polygon
• On the rectangularp-center problem
• Optimizing squares covering a set of points
• Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
• Simple \(O(n \log^{2} n)\) algorithms for the planar 2-center problem
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

Cited in

(7)

• Covering a set of line segments with a few squares
• Clustering geometrically-modeled points in the aggregated uncertainty model
• Efficient algorithms for computing one or two discrete centers hitting a set of line segments
• Corrigendum to: ``Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• Optimal covering and hitting of line segments by two axis-parallel squares
• 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: Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares

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