link

December 18, Tuesday
12:00 – 14:00

Networks and computational geometry – new results and future directions
Computer Science seminar
Lecturer : Dr. Liam Roditty
Lecturer homepage : http://www.wisdom.weizmann.ac.il/~liamr/
Affiliation : Faculty of Mathematics and Computer Science, Weizmann Institute of Science
Location : 202/37
Host : Dr. Danny Barash
There is an intrinsic connection between computational geometry and networking. In this talk I will describe theoretical results in computational geometry with practical implications in networking. More specifically, I will first present a new construction of geometric spanners that allows optimal routing between points in the plane. In the second part of the talk I will describe the first construction ever of a disk graph spanner. The practical importance of the later is enormous as it can serve as a topology for ad-hoc networks whose nodes have a *variable* transmission range.

The talk is based on the following papers:

1. Improved Algorithms for Fully Dynamic Geometric Spanners Lee-Ad Gottlieb (NYU) and Liam Roditty

2. Spanners for Ad Hoc Networks with Variable Transmission Range David Peleg (Weizmann) and Liam Roditty