Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal Euclidean spanners: really short, thin and lanky (Extended Abstract) (2013)
| Content Provider | CiteSeerX |
|---|---|
| Author | Elkin, Michael Solomon, Shay |
| Abstract | The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC’95 paper, titled“Euclidean spanners: short, thin and lanky”, Arya et al. [2] devised a construction of Euclidean (1 + ɛ)-spanners that achieves constant degree, diameter O(log n), weight O(log 2 n) · ω(MST), and has running time O(n · log n). This construction applies to n-point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time. This conjecture of Arya et al. became one of the most central open problems in the area of Euclidean spanners. Nevertheless, the only progress since 1995 towards its resolution was achieved in the lower bounds front: Any spanner with |
| File Format | |
| Language | English |
| Publisher Date | 2013-01-01 |
| Publisher Institution | STOC'13 |
| Access Restriction | Open |
| Subject Keyword | Optimal Euclidean Spanner Euclidean Spanner Central Open Problem Geometric Spanner Constant Degree Weight Bound Well-studied Parameter Logarithmic Factor Seminal Stoc Running Time N-point Constant-dimensional Euclidean Space |
| Content Type | Text |
| Resource Type | Technical Report |
