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 focused 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 Alex to schedule your talk. No talks are planned at the moment.

Past talks

• Nov 10, 11:00—11:40 (Zoom)
  Ruben van Niekerk: Parameterized Preprocessing for Weighted Maximization Problems.
  － Abstract
  

  Given a graph G, weight function ω: V(G) → N and integers k and t, the NP-hard parameterized decision problem Maximum Weighted Independent Set corresponds to whether G contains an independent set of size exactly k and weight at least t. In other words, is there a vertex subset X ⊆ V(G) of size k such that there are no edges between vertices of X and the total weight of vertices in X is at least t? On general graphs, this problem is known to be W[1]-complete. In this paper we consider this problem for planar graphs and introduce reduction rules to obtain an equivalent problem, in which the treewidth of the input graph is bounded. Then we will apply a dynamic programming algorithm to solve the problem on planar graphs in a running time only sub-exponential in complexity parameter k.
  
  In the second part we will present a kernel with $O(k^3)$ vertices. Kernelization is a provably effective technique for efficient preprocessing the input for the algorithm and has a lot of applications. We will obtain the kernel by deleting vertices that would never be part of a solution. This way we obtain an equivalent instance of the problem whose graph has at most $O(k^3)$ vertices.
  
  Finally, we will discuss generalizations of the techniques to the similar problems Maximum Weighted Induced Subgraph and Maximum weighted Induced d-Scattered Subgraph.

• Nov 03, 13:00—13:40 (Teams)
  Stijn Slot: Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds.
  － Abstract
  

  In the multi-robot motion planning problem the goal is to plan the motion of several robots operating in a common environment, while avoiding collisions with obstacles and other robots. In this thesis we consider the unlabeled version of the problem, where it is not specified which robot needs to move to which target location, for unit disc robots in a simple polygon. Previously it was shown that this problem, under the assumption of 4-unit separation between the start and target positions, always has a solution (Adler, de Berg, Halperin, and Solovey 2015).
  
  In this thesis we consider two types of separations: the monochromatic separation between start–start and target–target locations, and bichromatic separation between start–target locations.
  
  We show that the problem is always solvable assuming monochromatic separation 4 and bichromatic separation 3 for unit-disc robots in a simple workspace.

• Oct 28, 10:30—11:10 (Teams)
  Werner Kroneman: Pattern Formation Algorithms for Oblivious Robots in Presence of Measurement Errors.
  － Abstract
  

  Within the field of robotics, increasing interest is shown in the employment of distributed swarms of cheap, identical robots, as opposed to expensive and specialized monolithic units. Approaches vary from very practical to very theoretical; ranging from design of physical robots in the former case, to heuristics, simulations and to formal analysis in the latter. The OBLOT model has served as a de-facto standard framework for a subset of problems in the formal analysis setting.
  
  However, while useful in the study of the theoretical boundaries of different problems and solutions, a gap exists between abstract, formal models and the practical application of knowledge gathered therein to simulations and real robots.
  
  One such problem is that sensors may be inaccurate, seeing robots in a slightly different place than they really are. In this thesis, we explore such measurement errors in detail, and build an intuition for how to handle them by looking at how they affect specific solutions to the problems gathering and circle formation for three robots under the semi-synchronous scheduler, originally developed without taking measurement errors into account, and adapt them to produce a robust, bounded approximation of their original results.

• Sep 14, 15:00—15:40 (Teams)
  Wayan Traversat: Universal Coating by Programmable Matter in 3D.
  － Abstract
  

  Matter dictates the physical properties of everything around us. Orchestrated by atoms and the laws of nature, these physical properties are unique to each material. These properties are often static and hard to modify. The objective of programmable matter is to create a physical material that is programmable, scalable, autonomous, versatile, reconfigurable, robust to failures, and nanoscopic. Currently, programmable matter is not conceivable since particles are macroscopic in size, the advances of technology show promising results for the years to come. While we overcome the engineering challenges on our quest for miniaturization, engineers often sacrifice capabilities for size.
  
  To model these limited particles, we use the geometric amoebot model. The amoebot model provides a framework that defines how particles can interact with each other to solve a given problem. In the amoebot model it is agreed that particles: are anonymous entities; operate on a given graph; have limited computational power; have constant memory; interact and communicate strictly locally; have limited locomotion capabilities; and are activated by a scheduler.
  
  Under this model, we define a set of two problems: the Filling Problem and the Coating Problem. We will solve these problems under the amoebot model and under a sequential scheduler. We will prove that for any concurrent execution (asynchronous scheduler) with neighborhood locking, there exists a sequential ordering of actions that yield the same output. In the Filling Problem, an object forms a 2D perimeter of a bounded area to be filled by programmable particles. In this thesis, we present an algorithm that solves the Filling Problem in $O(n R)$ asynchronous rounds, where $R$ is the length of the longest chain of connected particles.
  
  In the Coating Problem, the surface of an object $O$ must be coated with uniform layers of programmable particles. The Coating Algorithm builds upon the Filling Algorithm to present a novel algorithm which solves the Coating Problem in $O(n R)$ asynchronous rounds, where $R$ is the length of the longest chain of connected particles. The algorithm only assumes that the initial set of particles in contact with the object to be coated is connected.

• Aug 27, 15:00—15:40 (Zoom)
  Kaj Suiker: Optimizing Staged Transitions for Scatter Plots.
  － Abstract
  

  Information visualization represents abstract data in a visual way. Scatter plots are common diagrams to represent static data, but there is no simple way for it to represent time varying data. To accomplish this, one method is to use a transition between a scatter plot from one time step to the next. This can be captured as an animation between two time steps. The resulting animation becomes harder to comprehend when there is a lack of structure between the points during their transition.
  
  This thesis constructs and implements a model to optimize complex animations of groups to be more understandable. We capture the understandability using principles of Gestalt theory, which drives the creation of the model. The model restricts the animation to three separate stages which have different purposes, such as merging, splitting, retaining proximity or maintaining the common fate principle.
  
  For these stages we must define groups in our scatter plots which will move together. This is accomplished using a clustering method. We developed an algorithm to compute waypoints used in the model, with multiple variable parameters. Using the waypoints we visualized two animation types, Separated and Bundled. Separated keeps the initial and the final shape of the groups stable during the animation. Bundled sacrifices some Gestalt principles by aggregating multiple trajectories together to improve the cluttering of the animation.
  
  The results show an improvement of the occlusion metric for both types with especially the Bundled type improving compared to the interpolated base animation. The conformity with Gestalt principles finds multiple improvements with the Separated type, showing the model’s emphasis on Gestalt. The Monte Carlo experiments show improvement in the Bundled type for the occlusion metric similar to other research in the field. For the Separated type the experiment shows its viability for further exploration, as it improves upon the interpolated base animation.

• Aug 25, 16:00—17:00 (Teams)
  Jules Wulms: Stability of Geometric Algorithms.
• Aug 14, 14:00—14:40 (Teams)
  Koen Klaren: Continuous Dynamic Time Warping for Clustering Curves.
  － Abstract
  

  Computing similarity between polygonal curves is an extensively studied problem. Two popular measures for this are dynamic time warping and the Fréchet distance. Dynamic time warping has the advantage of being less sensitive to outliers, while the Fréchet distance has the advantage of taking the continuous nature of the curves into account. A measure that combines these two advantages is continuous dynamic time warping (CDTW). So far, there has not been much research on how to compute CDTW.
  
  In this thesis we give a generalized definition for the CDTW distance between two curves and present three algorithms for computing it. The first algorithm, ApproxCDTW, gives an additive approximation guarantee on the computed similarity. The second algorithm, FastCDTW, provides a speed-up over the first algorithm, at the expense of the approximation guarantee. The third algorithm, ExactCDTW, computes the similarity exactly for one-dimensional curves. Finally, we demonstrate the utility of CDTW and the developed algorithms for clustering trajectories.

• Aug 13, 16:30—17:10 (Zoom)
  Jeroen Donners: Evacuating Robots from Ellipses and Regular Polygons.
  － Abstract
  

  The Evacuation problem considers a set of robots in a predefined environment, which contains an exit at an unknown location. The task is to find this exit, and have all robots reach that exit as quickly as possible. Various computational models can be considered, defined by the number of robots to be evacuated, and the communication model used by the robots. Previous work has considered the Evacuation problem on various geometric shapes like disks, equilateral triangles, and squares. Various lower and upper bounds have been shown on the Evacuation problem on these shapes, under various computational models.
  
  In this thesis, we continue investigating the Evacuation problem on other shapes, specifically an ellipse and a regular polygon. We analyze the worst-case evacuation time on an ellipse under the wireless communication model for 2 robots, and show that the evacuation time cannot be derived in terms of elementary functions. We continue by investigating the problem using a numerical approach, and hypothesize that the optimal starting point for the presented algorithm is trivial only for some specific ellipses. We discuss error bounds on the numerical simulations to support this claim, and continue the analytical approach to prove the presented hypothesis. We conclude the investigation of Evacuation on an ellipse by deriving for which ellipses a trivial starting point is optimal.
  
  We continue by investigating the Evacuation problem on a regular polygon for 2 robots under the wireless communication model. We present two lower bounds on the worst-case evacuation time, as functions of the number of corners in the regular polygon. We present two trivial evacuation algorithms, and derive their worst-case evacuation time analytically. We then present a third evacuation algorithm, which generalizes from the first two algorithms, and attempt to derive its worst-case evacuation time analytically. We finalize the investigation of the Evacuation problem on a regular polygon by presenting numerical results for the generalized evacuation algorithm, which shows that the optimal starting point for the presented algorithm is trivial only for some particular regular polygons.

• Aug 13, 10:20—11:00 (Zoom)
  Tom Peters: Comparison of Scheduler Models for Distributed Systems of Luminous Robots.
  － Abstract
  

  We investigate the computational power of multi-agent systems of autonomous point robots operating in the Euclidean plane. In particular, we compare four previously established models using pattern formation problems. In the first, the Oblot model, robots are oblivious and do not have persistent memory. They cannot communicate and have to base their movement entirely on the observed locations of the other robots. In the Lumi model, the robots are enhanced with a light that is visible both internally and externally, providing a constant amount of both a form of persistent memory as well as communication. In the last two models, FState and FComm, the light is only visible internally or externally respectively, each providing one of the two aspects this light offers: memory and communication. We investigate the relations between these models for two synchronous scheduler models: FSync and SSync. In the first model, all robots activate synchronously in rounds, in the second, the robots still activate in rounds, but not every robot activates each round. We show the computational relations between these four models under these two scheduler models when the robots are non-rigid, i.e. can be halted halfway during their movement, and are disoriented. Furthermore, in depth exploration of the relation between Lumi and FComm under SSync has revealed an additional scheduler model that is marginally stronger than SSync. For this new scheduler model the relation between Lumi and FComm becomes the same as under FSync.

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