β Scribed by Das, Gautam; Narasimhan, Giri
No coin nor oath required. For personal study only.
Gautam
Das q t Giri NarasimhanΓ bstract Let G = (V, 1?) be a n-vertex connected graph with positive edge weights. A subgraph G' is a t-spanner if for all u, v c V, the distance between u and v in the subgraph is at most t times the corresponding distance in G. We design an O(n log2 n) time algorithm which, given a set V of n points in kdimensional space, and any constant t > 1, prduces a t-spanner of the complete Euclidean graph of V. This algorithm retains the spirit of a recent 0(n3 log n)-time greedy algorithm which produces tspanners with a small number of edges and a small total edge weight; we use graph clustering techniques to achieve a more efficient implementation.Our ness 1 spanners have similar size and weight sparseaa those constructed by the greedy algorithm.
π SIMILAR VOLUMES
The problem of determining the Euclidean shortest path between two points in the presence of m simple polygonal obstacles is studied. An O( m 2 logn + nlogn ) algorithm is developed, where n is the total number of points in the obstacles. A simple O(E+T) algorithm for determining the visibility gra