Search

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]

In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n) time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n8 log n) and O(n15 log n) respectively. Apart from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio (1+1/k)2 in nO(k) time. [ABSTRACT FROM AUTHOR]

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O(d√log nlog log n) for 1D, that is, linear arrangement and O(d log nlog log n) for the 2D grid, where d is the maximum degree of hyperedges and n, the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O( ∜log n√kd log log n), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33x speed-up, on average, with only 1.31x degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee. [ABSTRACT FROM AUTHOR]

This paper deals with an important problem of mobile communication. The objective is to place k base stations of equal range on the boundary of a convex polygonal region P such that each point inside P is covered by at least one base station. We name this problem as region-cover(k) problem. A simplified form of this problem is the vertex-cover(k) problem, where the objective is to communicate with only the vertices of P instead of covering the entire polygon. We first present efficient algorithms for vertex-cover(2) and region-cover(2) problems, where the base stations are to be installed on a pair of specified edges. The time complexity of these algorithms are O(n log n) and O(n2) respectively, where n is the number of vertices in the polygon P. Next, we consider the case where k ≥ 3. We first concentrate on a restricted version of the vertex-cover(k) and region-cover(k) problems, where all the k base stations are to be installed on the same edge of P. Our proposed algorithm for the restricted vertex-cover(k) problem produces optimum result in O(min(n2,nk log n)) time, whereas the algorithm for the restricted region-cover(k) problem produces an (1 + ∊)-factor approximation result in $O((n + k){\rm log}(n + k) + n{\rm log}(\lceil \frac{1}{\epsilon} \rceil)$ time. Finally, we propose efficient heuristic algorithm for the unrestricted version of the region-cover(k) problem for k ≥ 3. Experimental results demonstrate that our proposed algorithm runs fast and produces near optimum solutions. [ABSTRACT FROM AUTHOR]

We study the problem of assigning non-overlapping geometric objects centered at a given set of points such that the sum of area covered by them is maximized. The problem remains open since 2002, as mentioned in a lecture slide of David Eppstein. In this paper, we have performed an exhaustive study on the problem. We show that, if the points are placed in R 2 then the problem is NP-hard even for simplest type of covering objects like disks or squares. In contrast, Eppstein (2017) [10] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping disks when the points are arbitrarily placed in R 2. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in R 2 gives a 2-approximation solution for the sum of area maximization problem. We also propose a PTAS for the same problem. Our results can be extended in higher dimensions as well as for a class of centrally symmetric convex objects. [ABSTRACT FROM AUTHOR]