Noon seminar

The informal research seminar of the ALGA group. Talks last roughly 25 minutes, with five extra minutes allocated for discussion. Many presentations are focussed on recent conference presentations, or practice talks for upcoming conferences. New members are often asked to give an overview of their field of research. Talks given by invited speakers may take up to 45-60 minutes including questions.

To be kept up-to-date about noon seminar presentations, please subscribe to the algoseminar-l mailing list.

This is the schedule for 2020. Schedules are available between 2005 and 2020.

• Presentation
• Master's defense
• Midterm
• Invited talk
• External talk
• Practice talk
• PhD defense
• Cancelled

Upcoming talks

Send an email to Jules to schedule your talk. No talks are planned at the moment.

Past talks

• Mar 10, 12:00—13:15 (cancelled)
  Dániel Oláh, Martijn Struijs, Jules Wulms: EuroCG practice talks.
  － Abstract
  

  EuroCG has 15 minute slots, so we have 12 min. talks with some time for questions and feedback.
  
  Dániel Oláh - Sometimes Reliable Spanners of Almost Linear Size
  Martijn Struijs - The Angular Blowing-a-Kiss Problem
  Jules Wulms - Repulsion Region in a Simple Polygon

• Mar 09, 12:00—13:15 (MF 11)
  Bram Custers, Aleksandr Popov, Sampson Wong: EuroCG practice talks.
  － Abstract
  

  EuroCG has 15 minute slots, so we have 12 min. talks with some time for questions and feedback.
  
  Bram Custers - Orthogonal Schematization with Minimum Homotopy Area
  Aleksandr Popov - Fréchet Distance Between Uncertain Trajectories: Computing Expected Value and Upper Bound
  Sampson Wong - Covering a Set of Line Segments with a Few Squares

• Mar 03, 12:15—13:15 (MF 12)
  Henk Alkema, Milutin Brankovic: EuroCG practice talks.
  － Abstract
  

  EuroCG has 15 minute slots, so we have 12 min. talks with some time for questions and feedback.
  
  Henk Alkema - Bitonicity of Euclidean TSP in Narrow Strips
  Milutin Brankovic - Local Routing in a Tree Metric 1-Spanner

• Feb 04, 12:45—13:15 (MF 13)
  Irene Parada: Extending simple and $1$-plane drawings of graphs.
  － Abstract
  

  Given a drawing $D(G)$ of a graph $G$, we study the problem of inserting a set of missing edges (edges of the complement of $G$) into $D(G)$, such that certain properties of the drawing are preserved. By Levi's Enlargement Lemma, in a pseudolinear drawing of a graph we can insert any set of missing edges in a way such that the result is again a pseudolinear drawing. In contrast, given a general simple drawing (in which two edges have at most one point in common) inserting a missing edge in a way such that the result is again a simple drawing is not always possible. We show that it is NP-complete to decide whether we can insert a missing edge in such a way. Moreover, the problem remains hard when restricting it to pseudocircular drawings.
  
  
  For $1$-plane drawings (simple drawings in which each edge is crossed at most once), deciding whether we can insert a missing edge such that the result is again a $1$-plane drawing is easily doable in polynomial time. However, it follows from the recognition of $1$-planarity problem that if we want to insert multiple edges simultaneously the problem becomes NP-complete. We finish the talk by showing that deciding whether any $k$ missing edges can be inserted into a $1$-plane drawing is FPT (with respect to $k$).

• Jan 22, 10:30—11:00 (MF 3.119)
  Koen van der Heijden: Strategies for Multi-Robot Motion Planning for Unlabeled Discs.
  － Abstract
  

  Recently, studies in multi-robot motion planning more and more often consider the unlabeled variant of the problem. Efficient algorithms that solve the unlabeled multi-robot motion planning problem have already been explored. Most recently, Adler et al. considered the case of unlabeled multi-robot motion planning within a simple polygon workspace. They show that under certain conditions, a motion schedule can be computed efficiently. In this thesis, we investigate their algorithm experimentally and aim to extend it in two directions. Firstly, we consider the case of non-simple workspace polygons. We show that, if we allow infinitely small holes, simultaneous movement of robots might be necessary. Secondly, we aim to improve the quality of the motion schedule in terms of quality metrics like the lengths of the paths traversed by the robots or how often they need to be activated. To compute improved schedules, we present an alternative approach to solving the pebble motion problem on graphs. We compare the resulting motion schedules experimentally.

• Jan 21, 12:45—13:15 (MF 12)
  Tim Ophelders: Continuous Hausdorff distance and its Computation.
• Jan 14, 12:45—13:15 (MF 13)
  Max Sondag: Computing Stable Demers Cartograms.
  － Abstract
  

  Cartograms are popular for visualizing numerical data for map regions. Maintaining correct adjacencies is a primary quality criterion for cartograms. When there are multiple data values per region (over time or different datasets) shown as animated or juxtaposed cartograms, preserving the viewer's mental-map in terms of stability between cartograms is another important criterion. We present a method to compute stable Demers cartograms, where each region is shown as a square and similar data yield similar cartograms. We enforce orthogonal separation constraints with linear programming, and measure quality in terms of keeping adjacent regions close (cartogram quality) and using similar positions for a region between the different data values (stability). Our method guarantees ability to connect most lost adjacencies with minimal leaders. Experiments show our method yields good quality and stability.