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

The participants.

The participants.

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

Tentative 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.