Loading...
Please wait, while we are loading the content...
Similar Documents
Paderborn , Germany Partitioned Neighborhood Spanners of Minimal Outdegree 1
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fischer, Matthias Lukovszki, Tamás Ziegler, Martin |
| Copyright Year | 1999 |
| Abstract | A geometric spanner with vertex set P IR D is a sparse approximation of the complete Euclidean graph determined by P. We introduce the notion of partitioned neighborhood graphs (PNGs), unifying and generalizing most constructions of spanners treated in literature. Two important parameters characterizing their properties are the outdegree k ¡ IN and the stretch factor f ¢ 1 describing the 'quality' of approximation. PNGs have been thuroughly investigated with respect to small values of f. We, on the other hand, present in this work results about feasable values of k — so to say the other extreme. The aim of minimizing this parameter rather than the first one arises from two observations: a) It determines the amount of space required for storing PNGs. b) Many algorithms employing a (previously constructed) spanner have running times depending on its outdegree. Our results include, for fixed dimensions D as well as asymptotically, upper and lower bounds on this optimal value of k. The upper bounds are constructive and yield efficient algorithms for actually computing the corresponding graphs. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://people.inf.elte.hu/lukovszki/Publ/cccg99full.pdf |
| Alternate Webpage(s) | http://wwwhni.upb.de/~tamas/cccg99full.pdf |
| Alternate Webpage(s) | https://people.inf.elte.hu/lukovszki/Publ/cccg99full.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
