The informal research seminar of the ALGO and AGA groups. 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.

**All noon seminar schedules: 2019 · 2018 · 2017 · 2016 · 2015 · 2014 · 2013 · 2012 · 2011 · 2010 · 2009 · 2008 · 2007 · 2006 · 2005**

**Quartile 4:Time: Tuesday 12:45-13:15**

Date | Room | Speaker | Title | |
---|---|---|---|---|

Apr 24 | Tuesday | MF 13 | Daniel Olah | $O(k)$-robust spanners in one dimension A geometric $t$-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most $t$ times the Euclidean distance between the points. Informally, a spanner is $O(k)$-robust if deleting $k$ vertices only harms $O(k)$ other vertices. We show that on any one-dimensional set of $n$ points, for any $\eps>0$, there exists an $O(k)$-robust $1$-spanner with $O(n^{1+\eps})$ edges. Previously it was only known that $O(k)$-robust spanners with $O(n^2)$ edges exists and that there are point sets on which any $O(k)$-robust spanner has $\Omega(n\log{n})$ edges. |

May 25 | Friday12:00-12:30 | MF 14 | Hein van Beers | Automatic Evaluation of Schematic Maps Schematic maps of public transportation networks need to adhere to certain design rules, which result in maps that are easy to read.
What these design rules should be, is subject to ongoing debate; in fact, it seems that different networks may require different rules and algorithms for schematization. To be able to compare maps designed according to different rules, it would be good if potentially relevant properties of given maps and proposed new designs could be quantified and measured, that is, computed.
The cognitive psychologist Maxwell Roberts listed a number of relevant properties, such as simplicity (of shapes), coherence and harmony (how different elements on the map fit together), balance (distribution of features over the map), adherence to relevant aspects of true topography, and similarity to other, familiar maps.
We tried to develop quantitative metrics for one or more of these abstract properties, to develop algorithms to compute these metrics for a given map, and to validate these metrics with a proof-of-concept implementation. |

May 28 | Monday13:00-13:30 | MF 13 | Tom van der Zanden | On the Exact Complexity of Polyomino Packing Polyomino packing is a classical type of puzzle in which we are asked to form a given target shape using polyomino pieces (i.e., pieces which are formed by gluing several squares edge-to-edge). In this talk, we study the complexity of this puzzle from the viewpoint of exact complexity, and give a tight characterization of when the puzzle is hard. We show that (assuming the Exponential Time Hypothesis) there is no $2^{o(n / log n)}$-time algorithm for deciding whether a set of polyominoes can be packed into a $3$-by-$n$ box. This is tight: there exists a strongly subexponential time algorithm for the $2$-by-$n$ case, while the general case (of deciding whether a set of polyominoes can be packed into any given shape with area $n$) can be solved in $2^{O(n / log n)}$ time. |

May 29 | Tuesday13:05-13:20 | MF 13 | Willem Sonke | A KDS for Discrete Morse-Smale Complexes The Morse-Smale complex of a terrain is a topological complex that provides information about the features of the terrain. It consists of the critical points (minima, saddles and maxima), together with steepest-descent paths from saddles to minima and steepest-ascent paths from saddles to maxima. We describe a kinetic data structure to maintain the Morse-Smale-complex for a triangulated terrain whose vertex heights change continuously. This can be used to efficiently analyze time-varying data. |

May 29 | Tuesday12:45-13:00 | MF 13 | Jules Wulms | Topological stability of kinetic k-centers We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model is very hard to work with. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove an upper and lower bound on the ratio between the maximum radius of an optimal but unstable solution and the maximum radius of a topologically stable solution---the topological stability ratio. |

Jun 7 | Thursday16:00-16:45 | MF 15 | Christian Scheideler | Models and Algorithms for Programmable Matter In general, programmable matter is any matter that has the ability to change its physical properties (like shape, density, moduli, conductivity, optical properties, etc.) based on user input or autonomous sensing. In my talk I will be focusing on programmable matter composed of nano-robots. In particular, I will present the amoebot model and show that it can be used effectively for typical applications like shape formation and coating. In addition to that, I will discuss possible extensions of the amoebot model like hybrid models based on nano-robots and tiles and present some recent results for these. |

Jun 8 | Friday13:30-14:00 | MF 14 | AurĂ©lien Ooms | Subquadratic Encodings for Point Configurations For most algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of some realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 (loglog n)^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/loglog n) query time without blowing up the space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension. |

**Quartile 3:Time: Tuesday 12:45-13:15**

Date | Room | Speaker | Title | |
---|---|---|---|---|

Feb 13 | Tuesday | MF 13 | Sudeshna Kolay | Kernelization for Problems in Incidence geometry In this talk, we explore the utility of the Veronese Mapping in obtaining upper bounds and/or lower bounds on kernelization algorithms in the field of Parameterized Complexity. In particular, we consider two problems: (i) Subset General Position, where the input is a set of n points and the optimization question is to find the largest subset of points that are in general position, for a fixed definition of general position; (ii) Hitting geometric sets, where the input is a geometric set system and the optimization question is to find the minimum sized subset of the universe that hits all objects of the set system. We study the parameterized decision versions of the problems under natural parameters, and in some cases design tight polynomial kernels. The highlight of this study is the use of Veronese mapping to extend the results for the above problems with respect to families of hyperplanes to results for the problems with respect to families of d-degree polynomials. Not only can this mapping be used to give upper bounds for kernelization algorithms, but sometimes also lower bounds, thereby providing tight kernelization algorithms for several families of problems in one go.
This is joint work with Jean-Daniel Boissonnat, Kunal Dutta and Arijit Ghosh. |

Feb 27 | Tuesday | MF 15 | Jeroen van Oorschot | Near-Dorling Cartograms An area cartogram is a map in which regions have been re-sized such that the area corresponds to a value, e.g. population, that should be mapped. A common way to generate cartograms is the diffusion-based method, however, the map this method produces have areas that might be difficult to compare because regions might have very different shapes. In contrast, in Dorling Cartograms each region is represented by a disk, which makes it easier to compare the areas of regions. However, since regions can no longer be identified by their shape, it is important to provide visual cues like correct adjacencies between regions to maintain recognizability. Unfortunately, it is not always possible to make every region a disk of the correct size while maintaining the adjacencies. In this thesis, we introduce near-Dorling cartograms: regions should be as round as possible, while maintaining all adjacencies between regions. We present an algorithm to create near-Dorling cartograms, which combines the diffusion method with a local area-preserving operation that reduces the boundary lengths of regions and in this way makes the regions more circular. We experimentally evaluate near-Dorling cartograms on various data sets on the countries of Europe and show that maps with mostly round shapes and correct adjacencies can be produced. |

Feb 27 | Tuesday12:15-12:45 | MF 15 | Irina Kostitsyna | An Optimal Algorithm to Compute the Inverse Beacon Attraction Region A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon is monotonically decreasing. A given beacon attracts a point if the point eventually reaches the beacon.
The problem of covering points of a polygon with a set of beacons can be viewed as a variation of the art gallery problem. Unlike most variations, the beacon attraction has an intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse
attraction region. The attraction region of a beacon is the set of points that it attracts and can be computed in linear time in simple polygons. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. In this talk, we present an optimal O(n log n) time algorithm to compute the inverse attraction region of a point inside a simple polygon. |

Mar 13 | Tuesday11:30-14:00 | MF 12 | Thom, Tim, Willem, Thom, Jules, Max, Aleks | EuroCG Practice Session 20 minute slots for talks, questions and feedback |

Mar 28 | Wednesday12:45 | MF 13 | Willem Sonke | Optimal Algorithms for Compact Linear Layouts Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this talk we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn nicely in a specified aspect ratio, while still clearly communicating the linearity of the layout. |

Apr 3 | Tuesday | MF 14 | Jules Wulms | A Framework for Algorithm Stability and its Application to Kinetic Euclidean MSTs We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms.
In this talk we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes.
Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability.
We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees. |

Apr 10 | Tuesday | MF 15 | Thom Castermans | Agglomerative Clustering of Growing Squares We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs.
We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm (where $\alpha$ is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward $O(n^2 \log n)$ time algorithm. |

**Quartile 2:Time: Tuesday 12:45-13:15**

Date | Room | Speaker | Title | |
---|---|---|---|---|

Jan 16 | Tuesday | TBA | Kevin Verbeek | CANCELLED |

Jan 30 | Tuesday12:30 | MF 14 | Robbert Mollevanger | Modular Robot Self-Reconfiguration The field of modular robot self-reconfiguration is an exciting and relatively young one. It concerns the hardware for these kinds of robots and the software to make them autonomously reconfigure into different shapes. This talk will give an overview of the field and present current state-of-the-art technologies, mainly focusing on the algorithmic side of things. |

Jan 31 | Wednesday12:30 | MF 15 | Bart van der Vecht | Self-organizing particle systems: shape formation by amoebots Amoebot is a recent model for self-organizing particle systems based on amoeba-like movement. This presentation focuses on research literature where this model has been used for the problem of shape formation. Different approaches to this problem will be presented, as well as common notions such as leader election, movement primitives and shape recovery. |

Feb 1 | Thursday12:10-13:30 | MF 4 | Marc Verhaegh | CANCELLED |