Search

Abstract: In this paper, we consider the problem of clustering a set of n finite point-sets in d-dimensional Euclidean space. Different from the traditional clustering problem (called points clustering problem where the to-be-clustered objects are points), the point-sets clustering problem requires that all points in a single point-set be clustered into the same cluster. This requirement disturbs the metric property of the underlying distance function among point-sets and complicates the clustering problem dramatically. In this paper, we use a number of interesting observations and techniques to overcome this difficulty. For the k-center clustering problem on point-sets, we give an -time 3-approximation algorithm and an -time -approximation algorithm, where m is the total number of input points and k is the number of clusters. When k is a small constant, the performance ratio of our algorithm reduces to for any . For the k-median problem on point-sets, we present a polynomial time -approximation algorithm. Our approaches are rather general and can be easily implemented for practical purpose. [Copyright &y& Elsevier]

Given an edge-weighted graph G = ( V , E ) and a subset R of V , a Steiner tree of G is a tree which spans all the vertices in R . A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G . As for λ -precise unit disk graphs we present a ( 10 + 1 λ ) -approximation algorithm, where λ is the length of the shortest edge in G . [ABSTRACT FROM AUTHOR]

Abstract: Given a set of non-parallel lines in the plane, a watchman route (tour) for is a closed curve contained in the union of the lines in such that every line is visited (intersected) by the route; we similarly define a watchman route (tour) for a connected set of line segments. The watchman route problem for a given set of lines or line segments is to find a shortest watchman route for the input set, and these problems are natural special cases of the watchman route problem in a polygon with holes (a polygonal domain). In this paper, we show that the problem of computing a shortest watchman route for a set of n non-parallel lines in the plane is polynomially tractable, while it becomes NP-hard in 3D. We give an alternative NP-hardness proof of this problem for line segments in the plane and obtain a polynomial-time approximation algorithm with ratio . Additionally, we consider some special cases of the watchman route problem on line segments, for which we provide exact algorithms or improved approximations. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of computing a minimum bending energy path (or MinBEP) in a simple corridor. Given a simple 2D corridor C bounded by straight line segments and arcs of radius 2r, the MinBEP problem is to compute a path P inside C and crossing two pre-specified points s and t located at each end of C so that the bending energy of P is minimized. For this problem, we first show how to lower bound the bending energy of an optimal curve with bounded curvature, and then use this lower bound to design a -approximation algorithm for this restricted version of the MinBEP problem. Our algorithm is based on a number of interesting geometric observations and approximation techniques on smooth curves, and can be easily implemented for practical purpose. It is the first algorithm with a guaranteed performance ratio for the MinBEP problem. [Copyright &y& Elsevier]

Abstract: For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of Pʼs vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of Set Cover and solved in time with a greedy -approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only cells, improving the running time of the algorithm to for simple polygons. In this paper we observe that, since minimum visibility decompositions for simple polygons have only sinks (i.e., cells of minimal visibility) (Bose et al., 2000), the running time of the algorithm can be further improved to . We then extend the result of Bose et al. to polygons with holes, showing that a minimum visibility decomposition of a polygon with h holes has only cells and only cells of minimal visibility. We exploit this result to obtain a faster algorithm for vertex guarding polygons with holes. We then show that, in the same time complexity, we can attain approximation factors of for simple polygons and for polygons with holes. [Copyright &y& Elsevier]

Abstract: In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain; that is, finding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in time, for a terrain with n vertices. Interestingly, however, the problem of finding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of unless . Moreover, we show that even a simplified version of the problem where we can have only three different types of intervals for the vertices is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community. [Copyright &y& Elsevier]

Abstract: In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles). [ABSTRACT FROM AUTHOR]

Abstract: This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of only to single triangles. We give efficient algorithms to optimize certain measures, including measures related to the area ratio of adjacent triangles, angle between outward normals of adjacent triangles (for polyhedral terrains), and number of convex vertices. Some other measures are shown to be NP-hard. These include maximum vertex degree, number of convex edges, and number of mixed vertices. For the latter two measures we provide, for any constant , factor approximation algorithms that run in and time (when the Delaunay triangulation is given). For minimizing the maximum vertex degree, the NP-hardness proof provides an inapproximability result. Our results are presented for the class of first order Delaunay triangulations, but also apply to triangulations where for every triangle at least two edges are fixed. The approximation result on maximizing the number of convex edges is also extended to k-th order Delaunay triangulations. [Copyright &y& Elsevier]

Abstract: In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm. [Copyright &y& Elsevier]

Abstract: A trajectory is a sequence of locations, each associated with a timestamp, describing the movement of a point. Trajectory data is becoming increasingly available and the size of recorded trajectories is getting larger. In this paper we study the problem of compressing planar trajectories such that the most common spatio-temporal queries can still be answered approximately after the compression has taken place. In the process, we develop an implementation of the Douglas–Peucker path-simplification algorithm which works efficiently even in the case where the polygonal path given as input is allowed to self-intersect. For a polygonal path of size n, the processing time is for or depending on the type of simplification. [Copyright &y& Elsevier]