Search

This paper deals with the problem of approximate point set pattern matching in 2D. Given a set P of n points, called sample set, and a query setQ of k points (k ≤ n), the problem is to find a match of Q with a subset of P under rigid motion (rotation and/or translation) transformation such that each point in Q lies in the ε-neighborhood of a point in P. The ε-neighborhood region of a point pi ϵ P is an axis-parallel square having each side of length ε and pi at its centroid. We assume that the point set is well-seperated in the sense that for a given ε> 0, each pair of points p, p' ϵ P satisfy at least one of the following two conditions (i) |x(p) − x(p')| ≥ ε, and (ii) |y(p) − y(p')| ≥ 3ε, and we propose an algorithm for the approximate matching that can find a match (if it exists) under rigid motion in O(n2k2(klogk + logn)) time. If only translation is considered then the existence of a match can be tested in O(nk2 logn) time. The salient feature of our algorithm for the rigid motion and translation is that it avoids the use of intersection of high degree curves. [ABSTRACT FROM AUTHOR]

Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem. The first problem is on computing k circles of minimum (common) radius with centers on L which can cover the members in P. We propose three algorithms for this problem. The first one runs in O(nklogn) time and O(n) space. The second one runs in O(nk + k2log3n) time and O(nlogn) space assuming that the points are sorted along L, and is efficient where k < < n. The third one is based on parametric search and it runs in O(nlogn + klog4n) time. The next one is on computing the minimum radius circle centered on L that can enclose at least k points. The time and space complexities of the proposed algorithm are O(nk) and O(n) respectively. Finally, we study the situation where the points are associated with k colors, and the objective is to find a minimum radius circle with center on L such that at least one point of each color lies inside it. We propose an O(nlogn) time algorithm for this problem. [ABSTRACT FROM AUTHOR]

Given a set P of n points on a 2D plane, the 1-corner empty corridor is a region inside the convex hull of P which is bounded by a pair of links; each link is an unbounded trapezium bounded by two parallel half-lines, and it does not contain any point of P. We present an improved algorithm for computing the widest empty 1-corner corridor that runs in O(n3log2n) time and O(n2) space. This improves the time complexity of the best known algorithm for the same problem by a factor of ]> [4]. [ABSTRACT FROM AUTHOR]

In this paper, we will study the problem of locating the center of smallest enclosing circle of a set P of n points, where the center is constrained to lie on a query line segment. The preprocessing time and space complexities of our proposed algorithm are O(n logn) and O(n) respectively; the query time complexity is O(log2n). We will use this method for solving the following problem proposed by Bose and Wang [3] - given r simple polygons with a total of m vertices along with the point set P, compute the smallest enclosing circle of P whose center lies in one of the r polygons. This can be solved in O( nlogn+mlog2n) time using our method in a much simpler way than [3]; the time complexity of the problem is also being improved. [ABSTRACT FROM AUTHOR]

The non-homogeneous version of the range assignment problem in Ad-Hoc wireless network is studied in the context of information broadcast and accumulation. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for a set of radio-stations when they are placed on a straight line. This improves time complexity of the existing results for the same two problems by a factor of n, where n is the number of radio-stations [2]. An easy to implement algorithm for the unbounded version of accumulation problem is also presented for the non-homogeneous version of the range assignment problem. Its worst case running time complexity is O(n2). The same algorithm works when the radio-stations are placed in Rd. [ABSTRACT FROM AUTHOR]

Given a set S of n pre-placed radio-stations and a source station s*, we consider two variations of minimum cost homogeneous range assignment problem for the 2-hops broadcast from s* to all the members in S, where the range assigned to a radio-station is either zero or a fixed value r. Thus, the cost of range assignment is proportional to the number of radio-stations having range r. The variations we study are (i) find the value of r and identify the radio-stations with range r such that the total cost is minimum, and (ii) given a real number r, check whether homogeneous 2-hops broadcast from s* to the members in S is possible with range r, and if so, then identify the smallest subset of S whom range r is to be assigned such that 2-hops broadcast from s* is possible. The first problem is solved in O(n3) time and space. But, the second one seems to be hard. We present a 3-factor approximation algorithm for this problem, which runs in O(n2) time. An O(n2) time heuristic algorithm for the second problem is also presented. Most of the times, it produces optimum result for randomly placed radio-stations. [ABSTRACT FROM AUTHOR]

An important problem of mobile communication is placing a given number of base-stations in a given convex region, and to assign range to each of them such that every point in the region is covered by at least one base-station, and the maximum range assigned is minimized. The algorithm proposed in this paper uses Voronoi diagram, and it works for covering a convex region of arbitrary shape. Experimental results justify the efficiency of our algorithm and the quality of the solution produced. [ABSTRACT FROM AUTHOR]

Given a set of n colored points with a total of m (≥ 3) colors in 2D, the problem of identifying the smallest color-spanning object is studied. We have considered two different shapes: (i) corridor, and (ii) rectangle of arbitrary orientation. Our proposed algorithms for the problems (i) and (ii) run in time O(n2logn) and O(n3logm) respectively. [ABSTRACT FROM AUTHOR]

Given a polyhedral terrain with n vertices, the shortest monotone descent path problem deals with finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points p = (x(p), y(p), z(p)) and q = (x(q), y(q), z(q)) on the path, if dist(s,p) < dist(s,q) then z(p) > z(q), where dist(s,p) denotes the distance of p from s along the aforesaid path. This is posed as an open problem in [3]. We show that for some restricted classes of polyhedral terrain, the optimal path can be identified in polynomial time. We also propose an elegant method which can return near-optimal path for the general terrain in polynomial time. [ABSTRACT FROM AUTHOR]