Search

Abstract We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP -complete, and give constant-factor approximation algorithms for those problems. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the dynamic version of covering the convex hull of a point set P in R2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O (log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2. [ABSTRACT FROM AUTHOR]

In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set of unit disks in . We first present a simple time 5-factor approximation algorithm for this problem, where is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time and respectively [M. De, G. K. Das, P. Carmi and S. C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disks, Int. J. of Computational Geometry and Appl., 22(6):461-477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to . A minor modification of this algorithm produces a -factor approximation algorithm in time. The same techniques can be applied to have a 3-factor and a -factor approximation algorithms in time and respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present -factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. [ABSTRACT FROM AUTHOR]

Prune-and-search is an excellent algorithmic paradigm for solving various optimization problems. We provide a general scheme for prune-and-search technique and show how to implement it in space-efficient manner. We consider both the in-place and read-only model which have several advantages compared to the traditional model of computation. Our technique can be applied to a large number of problems which accept prune-and-search. For examples, we study the following problems each of which has tremendous practical usage apart from theoretical implication: • computing the minimum enclosing circle (MEC) of a set of n points in R 2 , and • linear programming problems with two and three variables and n constraints. In the in-place setting, all these problems can be solved in O ( n ) time using O ( 1 ) extra-space. In the read-only setup, the time and extra-space complexities of the proposed algorithms for all these problems are O ( n polylog ( n ) ) and O ( polylog ( n ) ) , respectively. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in R 2 . First, we propose an O ( n 2 log n ) time in-place algorithm for finding the maximum clique of the intersection graph of a set of n axis-parallel rectangles of arbitrary sizes. For the intersection graph of fixed height rectangles, the time complexity can be slightly improved to O ( n log n + n K ) , where K is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is O ( m log n + n 2 ) where m is the number of edges in the disk graph, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is O ( n 2 + m ( n + K 3 ) ) ; m is the number of edges in the unit disk intersection graph and K is the size of the largest clique in that graph. It uses O ( n 3 ) time in-place computation of maximum matching in a bipartite graph, where the vertices are given in an array, and the existence of an edge between a pair of vertices can be checked by an oracle on demand (from problem specification) in O ( 1 ) time. This problem is of independent interest. All these algorithms need O ( 1 ) work space in addition to the input array. [ABSTRACT FROM AUTHOR]

Abstract: The coverage problem in wireless sensor networks addresses the problem of covering a region with sensors. Many different definitions of coverage are there in the literature depending on the goal of the coverage. In this paper, we address the problem of determining the quality of a sensor deployment against an intruder who can walk along a straight line. A line segment is said to be k-covered if it intersects the sensing regions of at least sensors distributed in . Similarly, it is said to be k-uncovered if it intersects the sensing regions, that is assumed to be circular, of at most sensors. We introduce two new metrics, smallest -covered line segment and longest -uncovered line segment, for measuring the quality of line coverage achieved by a sensor deployment. The intruder can walk a distance less than the smallest -covered line segment without ever being detected by sensors. So, this metric gives an estimate on the distance an intruder can walk in a straight line path before being detected by sensors. On the other side, the defender would want to deploy sensors so that the length of the longest -uncovered line segment is minimized. Given a deployment of sensors, we propose deterministic algorithms to determine the smallest -covered line segment and longest -uncovered line segment where the line segments can be of the following types: (i) axis-parallel (horizontal and vertical) line segments, (ii) line segments whose one endpoint is fixed and is of arbitrary orientation and (iii) arbitrary line segments. The time complexities for the first and second types of line segments are for both smallest -covered line segment and longest -uncovered line segment, where is the number of intersections among circles. For the arbitrary line segment case, the smallest -covered segment can be determined in time, whereas, the longest -uncovered segment can be determined in time, where and is a small value greater than or equal to . All our algorithms take linear space. [Copyright &y& Elsevier]