FUB-TAU Joint Research Workshop on Algorithms in Geometric Graphs
This five-day workshop brings together researchers from Israel and Berlin to work on problems related to geometric graphs.
Time & Location
Institut für Informatik
Takustraße 9, 14195 Berlin
Visitor information with travel directions
- Pankaj Agarwal
- Helmut Alt
- Bahareh Banyassady
- Jonas Cleve
- Claudia Dieckmann
- Omrit Filtser
- Frank Hoffmann
- Haim Kaplan
- Matya Katz
- Katharina Klost
- Klaus Kriegel
- Wolfgang Mulzer
- Liam Roditty
- Günter Rote
- Rachel Saban
- Nadja Scharf
- Micha Sharir
- Max Willert
- Decision trees for geometric problems:
- The recent result by Kane-Lovett-Moran shows that there are near-linear decision trees for k-SUM: [arXiv] [Micha Sharir's slides]
- There is a subquadratic decision tree for the discrete Fréchet distance: [Theorem 9.1]
- Can these techniques be interpreted more geometrically?
- Is there a near-linear decision tree for the discrete Fréchet distance
- Diameter of Unit Disk Graphs: Is there a subquadratic algorithm for computing the diameter of unit disk graphs?
- Sergio Cabello presented a subquadratic algorithm for the diameter of planar graphs: [arXiv]
- This was recently improved: [arXiv] [Haim Kaplan's slides]
- The best result for unit disk graphs is only slightly subquadratic: [arXiv]
- Can Cabello's methods be extended to unit disk graphs?
- Can we find a near-linear approximation algorithm for the diameter of disk graphs?
- The girth of disk graphs can be found in O(n log n) time. Can this be extended to other geometric graphs?
- Can we find approximation algorithms for interference minimization in sensor networks?
- Spanning ratio for Delaunay graphs: Can we find a short proof that the stretch factor of Delaunay graphs is less than 2?
- Can we find combinatorial bounds on the complexity of the transportation distance diagram for continuous distributions?
- Danzer's problem: Can we find a simple proof of Danzer's theorem: Any set of pairwise intersecting disks can be pierced by four points.
- Analysis of partial kd-trees
|Sunday, September 24|
|15:00–18:00||Welcome and Problem session|
|18:00||Dinner at Luise|
|Monday, September 25|
Micha Sharir: KLM
|Tuesday, September 26|
|19:00||Dinner at Restaurant Jungbluth|
|Wednesday, September 27|
|Thursday, September 28|
|13:30–15:00||Wrap-Up and Goodbye|
Wolfgang Mulzer, department of computer science.