---
_id: '18959'
abstract:
- lang: eng
  text: We investigate the problem of constructing spanners for a given set of points
    that are tolerant for edge/vertex faults. Let S be a set of $n$ points in the
    d-dimensional space and let k be an integer number. A k-edge/vertex fault tolerant
    spanner for S has the property that after the deletion of k arbitrary edges/vertices
    each pair of points in the remaining graph is still connected by a short path.<br><br>Recently
    it was shown that for each set S of n points there exists a k-edge/vertex fault
    tolerant spanner with O(k^2 n) edges which can be constructed in O(n log n + k^2
    n) time. Furthermore, it was shown that for each set S of n points there exists
    a k-edge/vertex fault tolerant spanner whose degree is bouned by O(c^k+1) for
    some constant c.<br><br>Our first contribution is a construction of a k-vertex
    fault tolerant spanner with O(kn) edges which is a tight bound. The computation
    takes O(n log^d-1 n + k n log log n) time. Then we show that the same k-vertex
    fault tolerant spanner is also k-edge fault tolerant. Thereafter, we construct
    a k-vertex fault tolerant spanner with O(k^2 n) edges whose degree is bounded
    by O(k^2). Finally, we give a more natural but stronger definition of k-edge fault
    tolerance which not necessarily can be satisfied if one allows only simple edges
    between the points of S. We investigate the question whether Steiner points help.
    We answer this question affirmatively and prove Theta(kn) bounds on the number
    of Steiner points and on the number of edges in such spanners.
author:
- first_name: Tamás
  full_name: Lukovszki, Tamás
  last_name: Lukovszki
citation:
  ama: 'Lukovszki T. New Results on Fault Tolerant Geometric Spanners. In: <i>Proceedings
    of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS</i>. ; 1999:193-204.
    doi:<a href="https://doi.org/10.1007/3-540-48447-7_20">10.1007/3-540-48447-7_20</a>'
  apa: Lukovszki, T. (1999). New Results on Fault Tolerant Geometric Spanners. In
    <i>Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99),
    LNCS</i> (pp. 193–204). <a href="https://doi.org/10.1007/3-540-48447-7_20">https://doi.org/10.1007/3-540-48447-7_20</a>
  bibtex: '@inproceedings{Lukovszki_1999, title={New Results on Fault Tolerant Geometric
    Spanners}, DOI={<a href="https://doi.org/10.1007/3-540-48447-7_20">10.1007/3-540-48447-7_20</a>},
    booktitle={Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99),
    LNCS}, author={Lukovszki, Tamás}, year={1999}, pages={193–204} }'
  chicago: Lukovszki, Tamás. “New Results on Fault Tolerant Geometric Spanners.” In
    <i>Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99),
    LNCS</i>, 193–204, 1999. <a href="https://doi.org/10.1007/3-540-48447-7_20">https://doi.org/10.1007/3-540-48447-7_20</a>.
  ieee: T. Lukovszki, “New Results on Fault Tolerant Geometric Spanners,” in <i>Proceedings
    of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS</i>, 1999,
    pp. 193–204.
  mla: Lukovszki, Tamás. “New Results on Fault Tolerant Geometric Spanners.” <i>Proceedings
    of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS</i>, 1999,
    pp. 193–204, doi:<a href="https://doi.org/10.1007/3-540-48447-7_20">10.1007/3-540-48447-7_20</a>.
  short: 'T. Lukovszki, in: Proceedings of the 6th Workshop on Algorithms an Data
    Structures (WADS’99), LNCS, 1999, pp. 193–204.'
date_created: 2020-09-03T13:03:45Z
date_updated: 2022-01-06T06:53:55Z
department:
- _id: '63'
doi: 10.1007/3-540-48447-7_20
language:
- iso: eng
page: 193-204
publication: Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99),
  LNCS
publication_identifier:
  isbn:
  - '9783540662792'
  - '9783540484479'
  issn:
  - 0302-9743
publication_status: published
status: public
title: New Results on Fault Tolerant Geometric Spanners
type: conference
user_id: '15415'
year: '1999'
...