Search Constraints
Filtering by:
Creator
Smid, Michiel
Remove constraint Creator: Smid, Michiel
Creator
Carmi, Paz
Remove constraint Creator: Carmi, Paz
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:
 Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
 Abstract:
 Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)spanner for P that has O(P) edges and chromatic number at most k. Finally, we consider an online variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
 Date Created:
 20080827

 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