Search

Given a convex polygon with n vertices, we study the problem of identifying a triangle with its smallest side as large as possible among all the triangles that can be drawn inside the polygon. We show that at least one of the vertices of such a triangle must coincide with a vertex of the polygon. We also propose an O (n 2) time algorithm to compute such a triangle inside the given convex polygon. [ABSTRACT FROM AUTHOR]

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]