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 4560 minutes including questions.
To be kept uptodate about noon seminar presentations, please subscribe to the algoseminarl mailing list.
All noon seminar schedules: 2019 · 2018 · 2017 · 2016 · 2015 · 2014 · 2013 · 2012 · 2011 · 2010 · 2009 · 2008 · 2007 · 2006 · 2005
Quartile 2:
Time: Tuesday 12:4513:15
Date  Room  Speaker  Title  

Nov 13  Tuesday  MF 12  Bram Custers  CANCELLED 
Nov 20  Tuesday  MF 14  Bram Custers  Subdivision Directional Fields We present a novel linear subdivision scheme for facebased tangent directional fields on triangle meshes. Our subdivision scheme is based on a novel coordinatefree representation of directional fields as halfedgebased scalar quantities, bridging the finiteelement representation with discrete exterior calculus. By commuting with differential operators, our subdivision is structurepreserving: it reproduces curlfree fields precisely, and reproduces divergencefree fields in the weak sense. Moreover, our subdivision
scheme directly extends to directional fields with several vectors per face by working on the branched covering space. Finally, we demonstrate how our scheme can be applied to directionalfield design, advection, and robust earth mover’s distance computation, for efficient and robust computation. 
Dec 7  Friday 13:3014:00  MF 15  Arjan van den Boogaart  Efficient computation of fiber optic networks The planning involved for fiber network infrastructure gives rise to various algorithmic problems.
Starting from a geographic dataset of houses and roads, we want to obtain a minimum cost solution for digging ditches, placing cables and distribution points such that each customer is connected to a distribution point.
We formulate this fiber network planning problem more formally and aim to automate this planning process.
We split this planning problem into 3 separate parts: Constructing a graph based on publicly available data, computing a Steiner tree, and placing capacitated medians to service all customers.
By constructing the graph in a specific way, we are able to calculate a nearoptimal Steiner tree on the graph very quickly.
We present a new optimal capacitated median algorithm on trees to place distribution points in $O(D \log D \cdot n + D\cdot k\cdot n)$ for total customer demand $D$, $n$ nodes and maximum capacity $k$.
The combined approach gives costefficient network plans within 10 minutes for areas with 2000 customers, replacing a majority of the manual labor required.

Quartile 1:
Time: Tuesday 12:4513:15
Date  Room  Speaker  Title  

Sep 11  Tuesday  MF 11  Dan Halperin  Separating a polyhedron from its singlepart mold: Optimal algorithms Casting is a manufacturing process where liquid material is poured
into a mold having the shape of a desired product. After the material
solidifies, the product is pulled out of the mold. We study the case
in which the mold is made of a single part and the object to be
produced is a threedimensional polyhedron. We give an algorithm that
decides whether a given polyhedron with n facets can indeed be
produced that way, and if so indicates how to orient the polyhedron
in the mold and in what direction the product can be pulled out
without breaking the mold. Our algorithm runs in linear time. The
best previous algorithm for this problem that we are aware of runs in
O(n^2) time. We also give an algorithm to find all possible pullout
directions, which runs in O(n log n) time, and show that it is
worstcase optimal.
Joint work with Prosenjit Bose, Zvi Geft, and Shahar Shamai

Oct 16  Tuesday 13:3014:00  MF 12  Thom Castermans  BolVis: Visualization for Textbased Research in Philosophy Traditional research in philosophy consists for a large part in conceptual analysis and close reading of texts. This is a precise but timeconsuming approach, in which the researcher focuses on one particular text passage or one philosophical concept from one or more works of an author. In this paper, we present BolVis, a visualization tool for textbased research in philosophy. BolVis allows researchers to determine quickly which parts of a text corpus are most relevant for their research by performing a semantic similarity search on words, sentences, and passages. It supports activities such as filtering, exploring the semantic context, comparing, performing close reading on selected passages, et cetera. Our approach enables indepth analysis of texts at a significantly greater scale than is possible by traditional means, thereby allowing researchers to gain in speed without compromising on precision. We demonstrate the usefulness of BolVis by applying it to a corpus consisting of about 11,000 pages of the writings of the Bohemian polymath Bernard Bolzano (17811848). Our use case addresses an open question about Bolzano's ideas concerning size equality for sets of natural numbers, and we show that the use of BolVis enabled us to find (at least a significant part of) the reason why he came to accept onetoone correspondence as a sufficient criterion for size equality. 
Oct 16  Tuesday  MF 12  Thom Castermans  Short Plane Supports for Spatial Hypergraphs A graph $G=(V,E)$ is a support of a hypergraph $H=(V,S)$ if every hyperedge induces a connected subgraph in $G$. Supports are used for certain types of hypergraph visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying established aesthetic quality criteria we are interested in finding supports that yield plane straightline drawings with minimum total edge length on the input point set $V$. We first show, from a theoretical point of view, that the problem is NPhard already under rather mild conditions as well as a negative approximability results. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILPbased approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Further, we evaluate the performance and tradeoffs between solution quality and speed of several heuristics relative to each other and compared to optimal solutions. 
Oct 29  Monday 13:0013:30  MF 15  Martijn Struijs  Curve clustering: hardness and algorithms Clustering point data is a wellstudied problem in computer science. Given a set $\mathcal{G}$ of $n$ points in Euclidean space, the Euclidean $k$center problem is to compute a set $\mathcal{C}$ of $k$ centers (not necessarily in $\mathcal{G}$) such that the maximum distance between a point in $\mathcal{G}$ and its nearest neighbouring center in $\mathcal{C}$ is minimized. The Euclidean $k$median problem is to compute a set $\mathcal{C}$ of $k$ centers such that the sum of distances between the points in $\mathcal{G}$ and their nearest neighbouring center in $\mathcal{C}$ is minimized. In this thesis, we consider these clustering problems for curves under the Fréchet, discrete Fréchet and Dynamic Time Warping (DTW) distance. We show that the $k$center problem for curves under the Fréchet and discrete Fréchet distance is NPhard and even NPhard to approximate within a factor of $2\epsilon$, even for $k=1$. We then extend our methods to show that computing the $k$median under the DTW and squared DTW distance is NPhard.
Finally, we consider algorithms for the related $(k,\ell)$center and $(k,\ell)$median problems, where we additionally require that all center curves in $\mathcal{C}$ have complexity at most $\ell$. First, we provide $(1+\epsilon)$approximation algorithms for the $(1,2)$center problem for continuous Fréchet distance and the $(k,\ell)$center problem for discrete Fréchet that run in polynomial time for fixed $k$ and $\ell$. Then, we give exact algorithms for the $(k,\ell)$center problem for the discrete Fréchet distance in 2D and the $(1,\ell)$median problem in 1D that run in polynomial time for fixed $k$ and $\ell$. 
Quartile 4:
Time: Tuesday 12:4513: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 onedimensional 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  Friday 12:0012: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 proofofconcept implementation. 
May 28  Monday 13:0013: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 edgetoedge). 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  Tuesday 13:0513:20  MF 13  Willem Sonke  A KDS for Discrete MorseSmale Complexes The MorseSmale 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 steepestdescent paths from saddles to minima and steepestascent paths from saddles to maxima. We describe a kinetic data structure to maintain the MorseSmalecomplex for a triangulated terrain whose vertex heights change continuously. This can be used to efficiently analyze timevarying data. 
May 29  Tuesday 12:4513:00  MF 13  Jules Wulms  Topological stability of kinetic kcenters We study the kcenter 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 kcenters. 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 solutionthe topological stability ratio. 
Jun 7  Thursday 16:0016: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 nanorobots. 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 nanorobots and tiles and present some recent results for these. 
Jun 8  Friday 13:3014: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 realRAM 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 wordRAM model. This encoding is spaceoptimal 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. 
Jun 19  Tuesday  MF 13  Aleksandar Markovic  NonMonochromatic and ConflictFree Colorings in Tree spaces and Planar Network Spaces A nonmonochromatic coloring (NMcoloring) of a set $S$ of intervals in $R^1$ is a coloring such that for any point $p$ in $R^1$, if the set $S_p$ of intervals containing $p$ contains at least two intervals, then it contains two intervals of different color. A conflictfree coloring (CFcoloring) of $A$ is defined similarly, except that $S_p$ should now contain an interval with a unique color.
It is well known that any set of $n$ intervals in $R^1$ admits a NMcoloring with two colors and a CFcoloring with three colors. We investigate generalizations of this result to colorings of objects in more complex $1$dimensional spaces, namely socalled tree spaces and planar network spaces. 
Jun 25  Monday 14:4515:15  MF 12  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
proofofconcept implementation. 
Jul 2  Monday 15:0015:30  MF 13  Ivo van Heck  Triangle Partition on graphs of bounded Cutwidth In the field of parameterized complexity the efficiency of algorithms is measured in terms of an explicit parameter instead of (only) the general concept of input size. This is particularly useful for difficult computational problems. For graph problems, three classical parameters are the cutwidth, pathwidth and treewidth, which are strongly related. Lokshtanov et al. have shown for many graph problems parameterized by both treewidth and pathwidth, the most efficient algorithms known are in fact optimal, assuming the Strong Exponential Time Hypothesis (SETH) holds. However, their lower bounds leave the cutwidth out of scope.
As such, we investigate the behaviour of one of the problems studied by Lokshtanov et al., TRIANGLE PARTITION, when parameterized by cutwidth. Based on the approach taken by Lokshtanov et al., we show that assuming SETH, there cannot exist an $epsilon > 0$ such that TRIANGLE PARTITION can be solved in $O*((2  epsilon)^{ctw(G)/2})$. This contrasts the results known for pathwidth and treewidth, which state TRIANGLE PARTITION cannot be solved in $O*((2  epsilon)^{pw(G)})$ and $O*((2  epsilon)^{tw(G)})$ respectively. Our second result is an algorithm which exploits the relation between the cutwidth and pathwidth of graphs where each edge is contained in a triangle. Using a simple preprocessing algorithm and a dynamic programming algorithm on a path decomposition of the resulting graph, we find an upper bound of $O*(2^{\frac{3}{4} ctw(G)})$.
In an attempt to improve on this bound, we investigate a communication variant of TRIANGLE PARTITION, where the graph is divided between two players. Their goal is to solve the problem using a minimum amount of communication. The parameter we use for TRIANGLE PARTITION COMMUNICATION is the number of edges connecting the parts of the two players. By constructing a large family of graphs, each requiring a unique message in any communication protocol, we show a lower bound of $\Omega(\frac{3^{k/3}}{k})$. Note the mismatch between this lower bound and the one found for the classic version, which suggests this approach is unlikely to prove fruitful with respect to finding an optimal algorithm for TRIANGLE PARTITION. Finally, we describe a communication algorithm based on a branching algorithm executed by both players, which leads to an upper bound of $O*(1.54369^k)$. 
Jul 3  Tuesday  MF 3  Jeroen Hoogers  Algorithms for Exploration of Architectural Design Spaces Recent developments in the field of Generative Design have allowed architects and designers to direct computers to solve difficult optimization problems. Generative Design programs can output designs which are optimized for certain designer specified criteria and constraints. However, these designs can only be influenced by modifying the underlying optimization parameters and constraints, making it difficult to influence their aesthetic quality and requiring the designer to have a deep understanding of both the domain and the design program.
We are interested in the generation and exploration of architectural designs by means of an evaluation process driven by user feedback. This thesis explores the application of Genetic Algorithms (GAs) as the primary method for achieving this goal. GAs facilitate the procedural generation and refinement of Architectural Designs through a simulated process of evolution. We represent both exterior building volumes and interior floorplans as structures that are evolvable using GAs.
To allow the user to make decisions on the direction of the architectural designs, we allow users to select individuals to evolve through a method called "Interactive Selection". Furthermore, we experiment with the concept of hybrid methods which combine both user selection and fitness based optimization GAs. Using this approach, we obtain results that are partly designed through interactive selection and partly optimized for feasibility. Solutions generated using these methods tend to be better optimized in terms of area size, space ratios and adjacencies than those exclusively based on interactive selection. However, the introduction of automatic optimization has been found to negatively influence the degree to which the user can control the solutions. Therefore, we aim to find a balanced approach in which a reasonable proportion of the designs are feasible without losing a significant degree of control and expressive quality. 
Jul 6  Friday 13:0013:30  MF 15  Arjan van den Boogaart  Optimizing fiber network planning For my graduation project I am working on optimizing the placement of cables and distribution points in fiber optics networks within the company ThePeopleGroup.
Planning the layout of fiber networks involves many different costs and constraints. The biggest cost is digging, which averages €11/m. Cables on the other hand only cost €0.1/m.
Starting from a geographic dataset of houses and roads, we want to obtain the cheapest way to dig ditches, place cables and distribution points such that each house is connected to a distribution point and the distribution points are connected to each other. 
Jul 10  Tuesday 14:0015:00  MF 13  Sudeshna Kolay  Separators for Subexponential Algorithms In Euclidean Geometry Many exact algorithms in geometric settings allow better running times than that in the general case. For example, most problems on planar graphs exhibit the "square root phenomenon". One of the reasons for better running times for algorithms in the geometric setting is the existence of good constructive separators, that help in designing algorithms based on the divideandconquer approach. This talk focuses on problems in Euclidean Geometry that allow subexponential exact algorithms. First, we consider the Rectilinear Steiner Tree problem in dimension $2$ and we use a graphic separator theorem, based on Robertson and Seymour's work on graph minor theory, to obtain a subexponential algorithm. However, due to constraints of the graphic separator theorem, we could not extend our strategy to higher dimensions. On the other hand, we consider the Euclidean TSP problem in dimension $d$. In order to design a subexponential algorithm for Euclidean TSP, we design a novel separator theorem that is purely based on Euclidean geometry and therefore can be generalized to all dimensions. 
Jul 31  Tuesday 10:0010:30  MF 14  Jeroen Hoogers  Algorithms for Exploration of Architectural Design Spaces Recent developments in the field of Generative Design have allowed architects and designers to direct computers to solve difficult optimization problems. Generative Design programs can output designs which are optimized for certain designerspecified criteria and constraints. However, these designs can only be controlled by modifying the underlying optimization parameters and constraints, making it difficult to influence their aesthetic quality and requiring the designer to have a deep understanding of both the problem domain and the design software.
We are interested in the generation and exploration of architectural designs by means of an evaluation process driven by user feedback. This thesis explores the application of Genetic Algorithms (GAs) as the primary method for achieving this goal. GAs facilitate the procedural generation and refinement of Architectural Designs through a simulated process of evolution. We represent both exterior building volumes and interior floorplans as structures that are evolvable using GAs.
To allow the user to make decisions on the direction of the architectural designs, we allow users to select individuals to evolve through a method called "Interactive Selection". Furthermore, we experiment with the concept of hybrid methods which combine both user selection and fitnessbased optimization GAs. Using this approach, we obtain results that are partly designed through interactive selection and partly optimized for feasibility. Solutions generated using these methods tend to be better optimized in terms of area, space ratios and adjacencies than those exclusively based on interactive selection. However, the introduction of automatic optimization is found to negatively influence the degree to which the user can control the solutions. Therefore, we aim to find a balanced approach in which a reasonable proportion of the designs are feasible without losing a significant degree of control and expressive quality. 
Aug 8  Wednesday 11:0011:30  MF 12  Timo Scholte  Graph Editing by Partial Complements The partial complement, introduced by Kaminski, Lozin, and Milanic, is a graph operator, that given a subset of the vertices, complements the subgraph induced on those vertices, whilst keeping the rest of the graph intact. Fomin et al. considered this operator in a graph editing setting. They studied the question “For a given graph $G$ and graph family $F$, is it possible to partially complement $G$ to $F$?". They showed that this was polynomial time solvable for various graph families, and proved that this problem is NPcomplete for $r$regular graphs. Their scope only includes a single application of the partial complement operator.
We extend this problem by allowing which multiple subsequent partial complements. Our goal is to find polynomial time algorithms, or fixed parameter tractable algorithms parameterized by the number of partial complements we allow, for various graph families. We show that a partial complement alters the rankwidth of a graph by at most $1$. This tells us that if we can express our problem in MSO1 logic and our goal family has bounded rankwidth, our problems are FPT parameterized by the number of partial complements we allow. We show that if $F$ is the family of Hfree simple graphs, this approach only works if $H$ is an induced subgraph of $P_4$.
We also pursuit algorithms that do not rely on MSO1 logic or rankwidth. To achieve this, we distinguish between simple graphs and unigraphs (an extension of simple graphs where every vertex is allowed to have at most one loop). Since unigraphs are allowed to have loops, a partial complement on a unigraph will also add or remove loops. This has nice algebraic implications, which we can exploit to show that we can determine how many partial complements are required to turn a unigraph into an edgeless graph in time $O(n^\omega)$, where omega is the matrix multiplication exponent. We use this result to find FPT algorithms for unigraphs to $P_3$ free reflexive unigraphs of at most $d$ connected components, simple graphs to edgeless simple graphs, and simple graphs to $P_3$free simple graphs of at most $d$ connected components, with running times $O(d^{2^k+d}/(d!) n^\omega)$, $O(2^{2^k}n^\omega + n^3)$, and $O((2d)^{2^{k+d}}/(d!) n^\omega + n^3)$, respectively. 
Aug 10  Friday 15:0015:30  MF 13  Rui Hu  Turing Kernelization for finding long paths and cycles In computer science, an NPhard problem is regarded as 'so hard' that no algorithm can solve it quickly. In order to improve the efficiency, we would like to preprocess the problem. If the preprocessing guarantees that it can reduce the size of the problem, as well as maintain the answer to the problem unchanged, then we call such preprocessing as 'kernelization' and we say such problem admits a 'kernel'. If the answer to the problem has size $k$, we desire its size to be reduced to some polynomial in $k$, after the kernelization.
As preprocessing, we want to create a smaller instance quickly without changing its answer. However this seems impossible for some problems, since the existence of these kernelizations violates some commonly believed complexitytheoretic assumptions. As an alternative, we try a preprocessing in a different way: we first split the instance of the hard problem into small pieces, with each piece of size $poly(k)$. We can solve each piece separately (and quickly), and solve the complete problem from the combination of answers to all pieces. This is formalized in the notion of Turing kernelization.
In this thesis we work on designing Turing Kernelization for two problems, namely the $k$cycle problem and the kpath problem. Following Jansen's DecomposeQueryReduce framework, we achieve a polynomial Turing Kernel for the $k$cycle problem where every piece has size $O(k^2)$, as well as a polynomial Turing Kernel for the $k$path problem where every piece has size $poly(k)$. We also show an idea that may improve the size of pieces to $O(k)$ for the $k$cycle problem. 
Quartile 3:
Time: Tuesday 12:4513: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 ddegree 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 JeanDaniel Boissonnat, Kunal Dutta and Arijit Ghosh. 
Feb 27  Tuesday  MF 15  Jeroen van Oorschot  NearDorling Cartograms An area cartogram is a map in which regions have been resized such that the area corresponds to a value, e.g. population, that should be mapped. A common way to generate cartograms is the diffusionbased 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 nearDorling cartograms: regions should be as round as possible, while maintaining all adjacencies between regions. We present an algorithm to create nearDorling cartograms, which combines the diffusion method with a local areapreserving operation that reduces the boundary lengths of regions and in this way makes the regions more circular. We experimentally evaluate nearDorling 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 12:1512: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  Tuesday 11:3014:00  MF 12  Thom, Tim, Willem, Thom, Jules, Max, Aleks  EuroCG Practice Session 20 minute slots for talks, questions and feedback 
Mar 28  Wednesday 12: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 timevarying 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 geovisualization. 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:4513:15
Date  Room  Speaker  Title  

Jan 16  Tuesday  TBA  Kevin Verbeek  CANCELLED 
Jan 30  Tuesday 12:30  MF 14  Robbert Mollevanger  Modular Robot SelfReconfiguration The field of modular robot selfreconfiguration 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 stateoftheart technologies, mainly focusing on the algorithmic side of things. 
Jan 31  Wednesday 12:30  MF 15  Bart van der Vecht  Selforganizing particle systems: shape formation by amoebots Amoebot is a recent model for selforganizing particle systems based on amoebalike 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 12:1013:30  MF 4  Marc Verhaegh  CANCELLED 