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

DOI10.1016/J.TCS.2018.10.013zbMATH Open1435.68353arXiv1709.04870OpenAlexW2963246055MaRDI QIDQ1737597FDOQ1737597

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)

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.

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

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

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)

Cites Work

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

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)