Noon seminar
The informal research seminar of the ALGO 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.
COVID-19 note
Some of the talks are currently conducted via Zoom. To avoid abuse, we do not distribute the join links publicly. To make the links appear in the list below, make sure you are signed in. Alternatively, you can find the join link in the announcement email.
This is the schedule for 2015. Schedules are available between 2005 and 2024.
- Presentation
- Master's defense
- Midterm
- Invited talk
- External talk
- Practice talk
- PhD defense
- Cancelled
Past talks
-
Dec 08, 11:30—12:00
(MF 4)
Aleksandar Markovic: Bin Packing and Discrepancy.
- Abstract
Two children are playing: the first one is trying to fit legos in as few boxes as possible, the other one is colouring some drawings as colourfully as possible with only two pencils. They are apparently playing two completely different games, but I will make them have fun together.
In a more mathematical formulation, I will show how to use Discrepancy theory to prove cool lower bounds on some techniques for the Bin Packing Problem. I will also present a nice programming question to find a small instance of the Bin Packing Problem that satisfies some necessary conditions and how to use it to create big instances with high integrality gaps.
-
Nov 30, 16:00—16:30
(MF 14)
Marieke Zantema: Compatible paths on point sets with two convex layers.
- Abstract
Consider a point set P in the plane, consisting of two convex layers. This means that all points that do not lie on the convex hull are in convex position. Two edges are said to cross each other if they share a point other than a common endpoint, and a Hamiltonian path is a path that visits all points. Two non-crossing Hamiltoninan paths on P are compatible if their union is non-crossing. We define the graph G(P) of which the vertices represent the non-crossing Hamiltonian paths on P and two vertices share an edge if the corresponding paths are compatible. We prove that the graph G(P) is connected.
-
Nov 24, 11:30—12:00
(cancelled)
Mehran Mehr: Faster Algorithms for Computing Plurality Points..
- Abstract
I'll talk about computational problems concerning so-called plurality points, a concept arising in social choice and voting theory and defined as follows.
We have a set of voters and a space of possible choices. Each voter has a utility function that indicates how much the voter likes a certain choice. Thus the utility function of each voter determines for any two choices from the given space which one is preferred by the voter or whether both choices are equally preferable. A (weak) plurality point is now defined as a choice such that there is no alternative choice that is preferred by more voters.
-
Nov 24, 09:30—10:00
(MF 14)
Hugo Snel: Cache-efficient algorithms for finite-element methods on arbitrary discretizations.
- Abstract
In the field of numerical simulation the finite element method is one of the most popular general purpose techniques for computing accurate solutions. Since memory latency is one of the most serious bottlenecks in high-performance computing, I/O-efficient algorithms which minimize this latency have been developed for finite element methods defined on grid-based discretizations by ordering the data accesses along a space-filling curve. In this thesis we investigate the design of I/O-efficient algorithms for finite element methods for arbitrary discretizations in two and three dimensions. In 2D we are successful in extending the 2D
algorithm to arbitrary subdivisions at the cost of doubling the traversal length. In 3D an optimal solution was not achieved, but a highly efficient solution which seems to scale well with the input size is still obtained by using heuristic approaches. Experimental evaluation shows that for tetrahedral subdivisions of point sets up to 80,000 the cache-miss rate can be reduced to as low as 5 procent.
-
Nov 23, 11:30—12:00
(MF 13)
Dirk Gerrits: Algorithmic Challenges in Circuit Board Assembly.
- Abstract
Since about a year ago I've worked for Assembléon Netherlands B.V. (now part of Kulicke and Soffa Industries, Inc.), a company in the Eindhoven area that produces pick-and-place machines. These machines outfit circuit boards with their resistors, capacitors, chips, LEDs, and other components. Given the design of the desired circuit board, it is an enormously complex optimization problem to have the machine assemble the board as quickly as possible. In this noon seminar I will try to illustrate these challenges and what I have done so far to improve the way our software tries to tackle them.
-
Nov 17, 11:30—12:00
(MF 11)
Sandor Kisfaludi-Bak: On the number of touching pairs in a set of planar curves.
- Abstract
Given a set of planar curves (Jordan arcs), each pair of which meets (either crosses or touches) exactly once, we establish an upper bound on the number of touchings. The bound depends on a parameter that is defined by the locations of the curve endpoints. Our method relies on finding special subsets of curves called quasi-grids in curve families. The talk is based on joint work with Peter Gyorgyi and Balint Hujter.
-
Nov 10, 11:30—12:00
(MF 4)
Bart Jansen: Fine-grained complexity and algorithm design.
- Abstract
During the fall semester of 2015, the Simons institute in Berkeley hosted a research program on "fine-grained complexity and algorithm design". In this informal talk I will describe what the program was about and mention some remarkable recent results in this area. In particular, I will show how elementary reductions can establish the equivalence of a class of fundamental combinatorial problems with respect to having "truly subcubic" algorithms, even though these problems seem to behave very differently at first sight.
-
Nov 09, 11:30—12:15
(MF 14)
Anna Lubiw: Flattening and Unfolding Convex Polyhedra.
- Abstract
The problem of flattening or unfolding a polyhedron has applications in manufacturing 3D shapes out of metal, cardboard or plastic. I will present two results: (1) a new method to cut the surface of a convex polyhedron and unfold it into a simple non-overlapping polygon in the plane; (2) a natural method to continuously flatten the surface of any convex polyhedron to the plane without cutting (e.g. imagine flattening a paper bag).
-
Oct 20, 11:30—12:15
(MF 12)
Erin Chambers: Flows in 1-crossing-minor-free graphs.
- Abstract
In this talk, we examine the maximum flow problem in directed H-minor-free graphs, where H can be drawn in the plane with one crossing, giving an O(n log n) algorithm (assuming a certain decomposition of the graph is given as input). This algorithm is part of a body of work whose goal is near-linear time algorithms to compute maximum flows and minimum cuts in generalizations of planar graphs, such as minor free graphs and topological graphs. Currently known algorithms and open problems in this area will both be surveyed. Joint work with David Eppstein.
-
Oct 13, 11:30—12:00
(cancelled)
Arthur van Goethem: Labelling groups of islands.
- Abstract
A variety of recurring geographic entities form collections of point, line or area features. Examples are groups of islands (Archipelago), relief features in deserts, periglacial lakes or geomorphological forms, such as drumlins and sinkholes. All these groups of features might be best identified with a single label. Surprisingly, the (automated) labelling of groups of features has received little attention so far. We investigate the labelling of feature groups by comparing manually generated labels to a set of formally defined, algorithmically optimal placements. By taking this systematic approach, we hope to detect if, and which, formal measures are, possibly subconsciously, used by cartographers. In the second part of the talk we will describe algorithms that compute algorithmically optimal labels for some of the possible problem settings. To be precise, we will look at straight-line and circular-arc labels that may (or may not) overlap a given set of islands. We present efficient algorithms to compute the line or circle minimizing the maximum distance to the islands, measured by the closest distance to each single island. Part of this presentation was presented at the International Cartographic Conference 2015, the other part involves work in progress.
-
Oct 09, 11:30—12:00
(MF 12)
Elena Khramtcova: On the cluster Voronoi diagrams.
- Abstract
Voronoi diagrams are famous geometric structures that encode proximity information and that are studied in computational geometry for decades. Are not all the questions about them settled? Surprisingly, this is not true, for example, for the cluster Voronoi diagrams. They are natural generalizations of the simplest Voronoi diagrams, and have both practical (VLSI design) and theoretical [2] applications.
Given a set of points (sites) in the plane, its (simplest) nearest- and farthest-point Voronoi diagrams are the subdivisions of the plane into regions such that each two points in the same region have the same nearest and farthest site, respectively. Roughly speaking, if we change sites to be clusters of points instead of points, the nearest-point Voronoi diagram becomes the Hausdorff Voronoi diagram, and the farthest-point Voronoi diagram becomes the farthest-color Voronoi diagram. These two diagrams do not satisfy the requirements of some standard construction methods, thus posing a challenge to enhance such methods. Although interesting on their own due to the above reason, cluster diagrams can serve as a machinery to solve some seemingly unrelated theoretical questions.
In this talk I will (1) review the state of the art of the cluster Voronoi diagrams, including our recent research on the randomized incremental construction algorithms for the Hausdorff Voronoi diagrams [1,3] and the current open problems; (2) show the connection between the cluster Voronoi diagrams and the stabbing circles problem [2].
[1] Panagiotis Cheilaris, Elena Khramtcova, Stefan Langerman, Evanthia Papadopoulou: A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters. LATIN 2014
[2] Merce Claverol, Elena Khramtcova, Evanthia Papadopoulou, Maria Saumell, Carlos Seara: Stabbing circles for sets of segments in the plane. ECG 2015
[3] Elena Khramtcova and Evanthia Papadopoulou: Randomized Incremental Construction for the Hausdorff Voronoi Diagram: CG week YRF 2015
-
Sep 28, 13:00—13:30
(MF 02)
Hans Bodlaender: Embedding small treewidth graphs in 2^O(n/log n) time.
- Abstract
In this paper, we study several problems that involve embedding of graphs of small treewidth. Each of these problems is NP-complete for graphs of treewidth 4 (or less, depending on the problem), and can be solved in 2^O(n/log n) time for graphs of bound treewidth, with a dynamic programming algorithm that exploits isomorphism of subgraphs. We also give matching lower bounds, assuming the Exponential Time Hypothesis. The studied problems include: finding tree or path decompositions of bounded with with a minimum number of bags; Intervalizing Colored Graphs; subgraph isomorphism (and variants: induced subgraphs, minors, ...) for graphs of bounded treewidth. This is joint work with Jesper Nederlof and Johan van Rooij.
-
Sep 17, 14:00—14:30
(MF 12)
Hugo Snel: Cache-efficient algorithms for finite element methods.
- Abstract
Cache-oblivious algorithms for element-oriented traversals have been developed by ordering the data accesses along a space-filling curve (SFC). Although the approach is optimal in the context of the IO-model, the drawback is the requirement that the mesh on which the computation is done has to match the recursively defined stucture of the SFC (e.g. triangular meshes and quadtree grids for 2D Sierpinski and Hilbert curves respectively). We present a new IO-optimal approach which is applicable to any planar subdivision, at the cost doubling the traversal length. Furthermore we explore the 3D variant and present a model which defines IO-efficient data access as a minimization problem. Using simple heuristics we are able to minimize the cache miss rate to as low as 5%.
-
Sep 10, 11:30—12:00
(MF 12)
Astrid Pieterse: Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT (Practice talk IPEC).
- Abstract
We present several sparsification lower and upper bounds for classic problems in graph theory and logic. For the problems 4-Coloring, (Directed) Hamiltonian Cycle, and (Connected) Dominating Set, we prove that there is no polynomial-time algorithm that reduces any n-vertex input to an equivalent instance, of an arbitrary problem, with bitsize O(n^{2-eps}) for eps > 0, unless NP is a subset of coNP/poly and the polynomial-time hierarchy collapses. These results imply that existing linear-vertex kernels for k-Nonblocker and k-Max Leaf Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be improved to have O(k^{2-eps}) edges, unless NP is a subset of coNP/poly. We also present a positive result and exhibit a non-trivial sparsification algorithm for d-Not-All-Equal-SAT. We give an algorithm that reduces an n-variable input with clauses of size at most d to an equivalent input with O(n^{d-1}) clauses, for any fixed d. Our algorithm is based on a linear-algebraic proof of Lov
-
Sep 08, 13:00—13:30
(Zwarte Doos 1.03)
Colin Lambrechts: Visibility Index Computations on Grid Terrains.
- Abstract
The visibility index of a cell c in a grid terrain T is defined as the percentage of cells that are visible from c. We consider the problem of computing the visibility index of all cells c in a grid terrain T of size n by n. To this end we first study the 1-dimensional version of the problem. We propose an algorithm that efficiently computes the visibility index in O(n log^2(n)) time for a given 1-dimensional terrain of size n. The algorithm is able to compute the visibility index of 500,000 cells within 150 seconds using real-life data sets, while the brute-force approach can only compute it for 5,000 cells within that time frame. Our proposed algorithm can be used to efficiently approximate the 2-dimensional version of the problem and we present our ideas on how to do that.
-
Sep 07, 13:00—13:30
(MF 12)
Tim Ophelders: Computing the Similarity Between Moving Curves (Practice talk ESA).
- Abstract
We study similarity measures for moving curves which can, for example, model changing coastlines or glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fr
-
Aug 17, 14:00—14:30
(MF 3.122)
Luuk de Visser: Point-Feature Labelling in the 1-Slider Model: A Fixed-Parameter Tractable Algorithm.
- Abstract
The placing of textual labels is a central task to many visualisation applications. The basic variant of this problem, known as the point-feature labelling problem, has been studied extensively in literature. However, as the problem is NP-hard for most variations, the vast majority of known algorithms give an approximate solution. As such, we present a fixed-parameter tractable algorithm for the point-feature labelling problem in the 1-slider model, returning a provably optimal solution. As parameter k, we use the maximum feedback edge number among all connected components of the graph underlying the problem. We also implemented our algorithm, and ran experiments using datasets of real-world examples.
-
Aug 17, 10:00—10:30
(MF 3.122)
Michel Cijsouw: Embedding Travel Time Cues in Schematic Maps.
- Abstract
A metro map is a type of diagram in which shapes of lines are simplified and geographic distances are often heavily distorted in order to provide a clear overview of a complex network. Because of these distortions, information about the original (real-world, geographically correct) map is lost. As a result, travelers could take unnecessary long routes when traveling from A to B. In order to tackle this problem we introduce several visual cues that aid the user in finding the fastest route from A to B.
-
Aug 14, 13:00—13:30
(MF 11/12)
Willem Sonke: Power graph visualizations for event logs.
- Abstract
In many situations nowadays event logs are generated. Those logs contain structured inform
-
Aug 14, 10:00—10:30
(MF 11/12)
Chris Hoedemakers: Geometric Spanner Networks.
- Abstract
A geometric t-spanner G is a weighted graph such that for every pair of vertices u,w ? G, it holds that ?_G(u,w)/d(u,w) ? t, where ?_G(u,w) denotes the weight of the shortest path from u to w in G, d(u,w) denotes the Euclidean distance between u and w, and t is a constant of at least 1. We refer to t as the spanning ratio of G. An additional spanner property that is desirable in certain application areas is the hop-diameter. A t-spanner with hop-diameter H is a spanner such that the short path between every pair of vertices consist of at most H edges.
-
Jul 21, 15:00—15:30
(MF 9)
Astrid Pieterse: Sparsification Upper and Lower Bounds For Graph Problems and Not-All-Equal SAT.
- Abstract
We will show that for a number of decision problems on graphs, polynomial-time algorithms
-
Jul 08, 11:30—12:00
(MF 6.132)
Ronald van Zon: Real-Time Collision Detection for Multiple Packaging Robots Using Monotonicity of Configur.
-
Jul 07, 11:30—12:00
(MF 14)
Roel van Happen: Enhancing schematic maps for improved route planning.
-
Jun 26, 15:00—15:30
(cancelled)
Willem Sonke: Power graph visualizations for event logs.
-
Jun 26, 13:00—13:30
(MF 11/12)
Thom Castermans: Visualizing Descriptive Status of Languages.
-
Jun 18, 13:00—13:30
(cancelled)
Sander Verdonschot: TBA.
-
Jun 16, 11:30—12:15
(MF13)
Erin Chambers: Measuring curve similarity using minimum area homologies.
-
Jun 11, 14:00—14:30
(MF 3.119)
Tim van Lieshout: New results on feed-link placement.
-
Jun 09, 11:30—12:00
(MF 15)
Michel Cijsouw: Embedding travel time cues in schematic maps.
-
Jun 03, 13:00—13:30
(MF 9)
Jasper Brekelmans: GlamMap: visualizing library metadata.
-
Jun 02, 11:30—12:30
(MF 15)
William Mackaness: The spatial Turing test in the context of urban exploration systems.
-
May 22, 11:00—11:30
(MF 14)
Astrid Pieterse: Sparsification Lower Bounds.
-
May 19, 11:30—12:00
(MF 15)
Rafael Cano: Mosaic Drawings and Cartograms.
-
May 18, 13:00—13:30
(cancelled)
Jasper Brekelmans: GlamMap: visualizing library metadata.
-
May 11, 11:30—12:00
(MF 15)
Colin Lambrechts: Visibility Index Computations on Grid Terrains.
-
May 07, 11:30—12:00
(MF 13)
Willem Sonke: Visualing event logs using graph-drawing techniques.
-
Apr 20, 13:00—13:30
(MF 6.131)
Per Kuijpers: Kinetic Geometric Problems with Smoothness Constraints.
-
Apr 20, 00:00—00:00
(cancelled)
Herman Haverkort: CANCELLED.
-
Apr 16, 11:30—12:00
(cancelled)
Kevin Verbeek: TBA.
-
Apr 02, 11:30—12:00
(cancelled)
Quirijn Bouts: TBA.
-
Mar 06, 13:00—16:00
(MF 13)
Mark de Berg: Partition Trees (Lecture series).
-
Mar 05, 11:00—13:00
(MF 12)
Quirijn Bouts, Thom Castermans, Tim Ophelders, Willem Sonke: Practice talks EuroCG.
-
Feb 26, 11:30—12:00
(MF 12)
Jasper Brekelmans: GlamMap: visualizing library metadata.
-
Feb 19, 11:30—12:00
(MF 12)
Tim Ophelders: The complexity of Snake.
-
Feb 05, 11:30—12:00
(MF 12)
Arthur van Goethem: On Streams and Incentives: A Synthesis of Individual and Collective Crowd Motion.
-
Jan 19, 13:00—13:30
(MF 3.141)
Max Konzack: Visualizing Interactions in Trajectories.
-
Jan 05, 13:00—13:30
(MF 2)
Ali Mehrabi: The intersection searching problem.