Search

Given a set P = { p 1 , p 2 , … , p n } of n points in Image 1 and each assigned with one of the given k distinct colors, we study the problem of finding the minimum width color spanning annulus of different shapes. Specifically, we consider the color spanning circular annulus ( C S C A ), axis-parallel square annulus ( C S S A ), axis parallel rectangular annulus ( C S R A ) , and equilateral triangular annulus of fixed orientation ( C S E T A ) . The time complexities of the proposed algorithms for the respective problems are (i) O ( n 3 log ⁡ n ) for C S C A , (ii) O ( n 3 + n 2 k log ⁡ k ) for C S S A , (iii) O ( n 4 ) for C S R A , and (iv) O ( n 2 k ) for C S E T A . [ABSTRACT FROM AUTHOR]

Algorithms and Discrete Mathematics - celebrating the silver jubilee of IITG Guwahati. [Extracted from the article]

Abstract: The shortest paths on the surface of a convex polyhedron can be grouped into equivalence classes according to the sequences of edges, consisting of n-triangular faces, that they cross. Mount (1990) proved that the total number of such equivalence classes is . In this paper, we consider descending paths on the surface of a 3D terrain. A path in a terrain is called a descending path if the z-coordinate of a point p never increases, if we move p along the path from the source to the target. More precisely, a descending path from a point s to another point t is a path Π such that for every pair of points and on Π, if then . Here denotes the distance of p from s along Π. We show that the number of equivalence classes of the shortest descending paths on the surface of a convex terrain is . We also discuss the difficulty of finding the number of equivalence classes on a convex polyhedron. [Copyright &y& Elsevier]

Let P be a set of n points, where each point is colored with one of the k possible colors. We present efficient algorithms to preprocess P such that for a given query point q , we can quickly identify the smallest color spanning object of the desired type containing q. In this paper, we focus on (i) intervals, (ii) axis-parallel square, (i i i) axis-parallel rectangle, (i v) equilateral triangle of fixed orientation and (v) circle, as our desired type of objects. [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]

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: This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined -neighborhood region around some point in P. The proposed algorithm for the exact matching needs space and preprocessing time. The existence of a match for a given query set Q can be checked in time in the worst-case, where is the maximum number of equidistant pairs of point in P. For a set of n points, may be in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the -neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are and , respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition. [Copyright &y& Elsevier]

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]