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
24–28.09.2017
Institut für Informatik
Takustraße 9, 14195 Berlin
Room 125
Visitor information with travel directions
Participants
- 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
Problems
- 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
Program
| Sunday, September 24 | |
| 15:00–18:00 | Welcome and Problem session |
| 18:00 | Dinner at Luise |
| Monday, September 25 | |
| 10:00–11:00 |
Micha Sharir: KLM |
| 11:00–12:00 |
Work session |
| 12:30–13:30 | Lunch |
| 13:30–15:00 | Work session |
| 15:00–15:30 | Coffee |
| 15:30–17:00 | Work session |
| Tuesday, September 26 | |
| 10:00–11:00 | Progress report |
| 11:00–12:00 | Work session |
| 12:30–13:30 | Lunch |
| 13:30–15:00 | Work session |
| 15:00–15:30 | Coffee |
| 15:30–17:00 | Work session |
| 19:00 | Dinner at Restaurant Jungbluth |
| Wednesday, September 27 | |
| 10:00–12:00 | Work session |
| 12:30–13:30 | Lunch |
| 13:30–15:00 | Work session |
| 15:00–15:30 | Coffee |
| 15:30–17:00 | Work session |
| Thursday, September 28 | |
| 10:00–12:00 | Work session |
| 12:30–13:30 | Lunch |
| 13:30–15:00 | Wrap-Up and Goodbye |
Contact Information
Wolfgang Mulzer, department of computer science.