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.
Time: Tuesday 12:45-13:15
|Feb 13||Tuesday||MF 13||Sudeshna Kolay|| |
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|| |
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||Tuesday |
|MF 15||Irina Kostitsyna|| |
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||Tuesday |
|MF 12||Thom, Tim, Willem, Thom, Jules, Max, Aleks|| |
20 minute slots for talks, questions and feedback
Time: Tuesday 12:45-13:15
|Jan 16||Tuesday||TBA||Kevin Verbeek||CANCELLED|
|Jan 30||Tuesday |
|MF 14||Robbert Mollevanger|| |
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||Wednesday |
|MF 15||Bart van der Vecht|| |
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||Thursday |
|MF 4||Marc Verhaegh||CANCELLED|