Search

In the paper "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", Theor. Comput. Sci. 769 (2019) 63–74, the LHIT problem is proposed as follows: For a given set of non-intersecting line segments L = { ℓ 1 , ℓ 2 , ... , ℓ n } in Image 1 , compute two axis-parallel congruent squares S 1 and S 2 of minimum size whose union hits all the line segments in L , and a linear time algorithm was proposed. Later it was observed that the algorithm has a bug. In this corrigendum, we corrected the algorithm. The time complexity of the corrected algorithm is O (n 2). [ABSTRACT FROM AUTHOR]

Highlights • Algorithms for covering and hitting a given set of line segments by two congruent squares of minimum size is studied. • The algorithm produces optimum solution by sequentially reading the input array (read only) twice. • The extra space complexity of the algorithm is O (1). • A restricted version of covering is also studied where each object is to be completely covered by at least one square. • This algorithm gives 2 approximation result to cover/hit the segments with two congruent disks of minimum size. Abstract This paper discusses the problem of covering and hitting a set of line segments L in R 2 by a pair of axis-parallel congruent squares of minimum size. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithms assume that the input segments are given in a read-only array. For each of these problems (i.e. covering , hitting and restricted covering problems), our proposed algorithm reports the optimum result by executing only two passes of reading the input array sequentially. All these algorithms need only O (1) extra space. The solution of these problems also give a 2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we have designed a randomized algorithm to generate a random polygon P from a given set S={p 1, p 2,. . ., p n} of n points lying on a two dimensional plane. As a preprocessing task, we first compute the convex hull layers from the set S in O(n 2) time by modifying the well known Jarvis march algorithm. Next, we execute our algorithm taking the convex hull layers as input to generate random polygons over given point set. This is a Las-Vegas randomized algorithm with O(nℓogn) time which is much improved over the existing one. We also give a procedure to count the total number of different polygons that can be generated by our algorithm. This number help us to calculate the probability of generating a unique polygon in each execution which measure the randomness of our algorithm. [Copyright &y& Elsevier]