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]

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of n points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) staircases. A monotonically rising staircase is a sequence of alternatingly horizontal and vertical line segments from the bottom-left corner of the floor to its top-right corner such that for every pair of points α=(xα,yα) and β=(xβ,yβ) on the staircase, xα⩽xβ implies yα⩽yβ. A monotonically falling staircase can similarly be defined from the bottom-right corner of the floor to its top-left corner. An empty staircase polygon is a MESP if it is not contained in another larger empty staircase polygon. The problem of recognizing the largest MESP is formulated using permutation graph, and a simple O(n3) time algorithm is proposed. Next, based on certain novel geometric properties of the problem, an improved algorithm is developed that identifies the largest MESP in O(n2) time and space. The algorithm can be easily tailored for identifying the widest MESP in a similar environment. The general problem of locating the largest area/width MESP among a set of isothetic polygonal obstacles, can be solved easily. These geometric optimization problems have several applications to VLSI layout design, robot motion planning, to name a few. [Copyright &y& Elsevier]

In the acrophobic guard watchtower problem for a polyhedral terrain, a square axis-aligned platform is placed on the top of a tower whose bottom end-point lies on the surface of the terrain. As in the standard watchtower problem, the objective is to minimize the height (i.e., the length) of the watchtower such that every point on the surface of the terrain is weakly visible from the platform placed on the top of the tower. In this paper, we show that in R 2 the problem can be solved in O (n) time, and in R 3 it takes O (n log ⁡ n) time, where n is the total number of vertices of the terrain. [ABSTRACT FROM AUTHOR]

Given a set of n colored points in IR2 with a total of m (3 ≤ m ≤ n) colors, the problem of identifying the smallest color-spanning object of some predefined shape is studied in this paper. We shall consider two different shapes: (i) corridor and (ii) rectangle of arbitrary orientation. Our proposed algorithm for identifying the smallest color-spanning corridor is simple and runs in O(n2log n) time using O(n) space. A dynamic version of the problem is also studied, where new points may be added, and the narrowest color-spanning corridor at any instance can be reported in O(mn(α(n))2log m) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in O(n3log m) time and O(n) space. [ABSTRACT FROM AUTHOR]

Abstract: 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 and on the path, if then , where denotes the distance of p from s along the aforesaid path. This is posed as an open problem by Berg and Kreveld [M. de Berg, M. van Kreveld, Trekking in the Alps without freezing or getting tired, Algorithmica 18 (1997) 306–323]. We show that for some restricted classes of polyhedral terrain, the optimal path can be identified in polynomial time. [Copyright &y& Elsevier]

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]

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]