Search Constraints
1  3 of 3
Number of results to display per page
Search Results

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
 Abstract:
 It is wellknown that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in ddimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
 Date Created:
 20081027

 Resource Type:
 Conference Proceeding
 Creator:
 Farshi, Mohammad, Abam, Mohammad Ali, Smid, Michiel, and Carmi, Paz
 Abstract:
 A SemiSeparated Pair Decomposition (SSPD), with parameter s > 1, of a set is a set {(A i ,B i )} of pairs of subsets of S such that for each i, there are balls and containing A i and B i respectively such that min ( radius ) , radius ), and for any two points p, q S there is a unique index i such that p A i and q B i or viceversa. In this paper, we use the SSPD to obtain the following results: First, we consider the construction of geometric tspanners in the context of imprecise points and we prove that any set of n imprecise points, modeled as pairwise disjoint balls, admits a tspanner with edges which can be computed in time. If all balls have the same radius, the number of edges reduces to . Secondly, for a set of n points in the plane, we design a query data structure for halfplane closestpair queries that can be built in time using space and answers a query in time, for any ε> 0. By reducing the preprocessing time to and using space, the query can be answered in time. Moreover, we improve the preprocessing time of an existing axisparallel rectangle closestpair query data structure from quadratic to nearlinear. Finally, we revisit some previously studied problems, namely spanners for complete kpartite graphs and lowdiameter spanners, and show how to use the SSPD to obtain simple algorithms for these problems.
 Date Created:
 20090914

 Resource Type:
 Conference Proceeding
 Creator:
 Gudmundsson, Joachim, Farshi, Mohammad, Smid, Michiel, De Berg, Mark, and Ali Abam, Mohammad
 Abstract:
 Let (S,d) be a finite metric space, where each element p S has a nonnegative weight w(p). We study spanners for the set S with respect to weighted distance function d w , where d w (p,q) is w(p)+d(p,q)+wq if p≠q and 0 otherwise. We present a general method for turning spanners with respect to the dmetric into spanners with respect to the d w metric. For any given ε>0, we can apply our method to obtain (5+ε)spanners with a linear number of edges for three cases: points in Euclidean space ℝ d , points in spaces of bounded doubling dimension, and points on the boundary of a convex body in ℝ d where d is the geodesic distance function. We also describe an alternative method that leads to (2+ε)spanners for points in ℝ d and for points on the boundary of a convex body in ℝ d . The number of edges in these spanners is O(nlogn). This bound on the stretch factor is nearly optimal: in any finite metric space and for any ε>0, it is possible to assign weights to the elements such that any noncomplete graph has stretch factor larger than 2ε.
 Date Created:
 20091102