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: 2018 · 2017 · 2016 · 2015 · 2014 · 2013 · 2012 · 2011 · 2010 · 2009 · 2008 · 2007 · 2006 · 2005**

**Quartile 2:Time: Tuesday 11:30-12:00**

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

Nov 9 | Monday11:30-12:15 | MF 14 | Anna Lubiw | Flattening and Unfolding Convex Polyhedra 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). |

Nov 10 | Tuesday | MF 4 | Bart Jansen | Fine-grained complexity and algorithm design 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 17 | Tuesday | MF 11 | Sandor Kisfaludi-Bak | On the number of touching pairs in a set of planar curves 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 23 | Monday11:30 | MF 13 | Dirk Gerrits | Algorithmic Challenges in Circuit Board Assembly 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 24 | Tuesday | MF 4 | Mehran Mehr | CANCELLED |

Nov 24 | Tuesday9:30-10:00 | MF 14 | Hugo Snel | Cache-efficient algorithms for finite-element methods on arbitrary discretizations 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 30 | Monday16:00-16:30 | MF 14 | Marieke Zantema | Compatible paths on point sets with two convex layers 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. |

Dec 8 | Tuesday | MF 4 | Aleksandar Markovic | Bin Packing and Discrepancy 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. |

Jan 12 | Monday11:30 | MF 12 | Mikkel Abrahamsen | Common Tangents of Two Simple Polygons in Linear Time and Constant Workspace We describe algorithms for computing the common tangents of two disjoint simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies on the same side of the line. A common tangent is a tangent of both polygons. If the polygons are on the same side of the tangent, it is an outer common tangent. Otherwise, it is a separating common tangent. Each polygon is given as a read-only array of its corners in cyclic order. The algorithms detect if outer or separating tangents do not exist. This implies that it is possible in linear time and constant workspace to detect if the convex hulls of the polygons are disjoint, and if not, whether one convex hull is contained in the other. The algorithms are short and simple, but the proofs that they work are non-trivial. |

Jan 19 | Monday11:30 | MF 12 | Irina Kostitsyna | CANCELLED |

Jan 26 | Monday11:30 | TBA | Bettina Speckmann | CANCELLED |

**Quartile 1:Time: Tuesday 11:30-12:00**

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

Sep 7 | Monday13:00-13:30 | MF 12 | Tim Ophelders | Computing the Similarity Between Moving Curves (Practice talk ESA) 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échet distance between surfaces. While the Fréchet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality. |

Sep 8 | Tuesday13:00-13:30 | Zwarte Doos 1.03 | Colin Lambrechts | Visibility Index Computations on Grid Terrains 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 10 | Thursday11:30 | MF 12 | Astrid Pieterse | Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT (Practice talk IPEC) 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ász that bounds the number of hyperedges in critically 3-chromatic d-uniform n-vertex hypergraphs by (n choose d-1). We show that our kernel is tight under the assumption that NP is not a subset of coNP/poly. |

Sep 17 | Thursday14:00-14:30 | MF 12 | Hugo Snel | Cache-efficient algorithms for finite element methods 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 28 | Monday13:00-13:30 | MF 02 | Hans Bodlaender | Embedding small treewidth graphs in 2^O(n/log n) time 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. |

Oct 9 | Friday11:30 | MF 12 | Elena Khramtcova | On the cluster Voronoi diagrams 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 |

Oct 13 | Tuesday | MF 11 | Arthur van Goethem | CANCELLED |

Oct 20 | Tuesday11:30-12:15 | MF 12 | Erin Chambers | Flows in 1-crossing-minor-free graphs 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. |

**Quartile 4:Time: Tuesday 11:30-12:00**

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

Apr 20 | Monday13:00-13:30 | MF 6.131 | Per Kuijpers | Kinetic Geometric Problems with Smoothness Constraints |

Apr 20-24 | TBA | MF 12 | Herman Haverkort | CANCELLED |

May 7 | Thursday11:30 | MF 13 | Willem Sonke | Visualing event logs using graph-drawing techniques |

May 11 | Monday11:30 | MF 15 | Colin Lambrechts | Visibility Index Computations on Grid Terrains |

May 18 | Monday13:00-13:30 | MF 6.131 | Jasper Brekelmans | CANCELLED |

May 19 | Tuesday | MF 15 | Rafael Cano | Mosaic Drawings and Cartograms |

May 22 | Friday11:00-11:30 | MF 14 | Astrid Pieterse | Sparsification Lower Bounds |

Jun 2 | Tuesday11:30-12:30 | MF 15 | William Mackaness | The spatial Turing test in the context of urban exploration systems |

Jun 3 | Wednesday13:00-13:30 | MF 9 | Jasper Brekelmans | GlamMap: visualizing library metadata |

Jun 9 | Tuesday | MF 15 | Michel Cijsouw | Embedding travel time cues in schematic maps |

Jun 11 | Thursday14:00-14:30 | MF 3.119 | Tim van Lieshout | New results on feed-link placement |

Jun 16 | Tuesday11:30-12:15 | MF13 | Erin Chambers | Measuring curve similarity using minimum area homologies |

Jun 18 | Thursday13:00-13:30 | MF 14 | Sander Verdonschot | TBA |

Jun 26 | Friday15:00-15:30 | MF 11/12 | Willem Sonke | CANCELLED |

Jun 26 | Friday13:00-13:30 | MF 11/12 | Thom Castermans | Visualizing Descriptive Status of Languages |

Jul 7 | Tuesday | MF 14 | Roel van Happen | Enhancing schematic maps for improved route planning |

Jul 8 | Wednesday11:30 | MF 6.132 | Ronald van Zon | Real-Time Collision Detection for Multiple Packaging Robots Using Monotonicity of Configur |

Jul 21 | Tuesday15:00-15:30 | MF 9 | Astrid Pieterse | Sparsification Upper and Lower Bounds For Graph Problems and Not-All-Equal SAT We will show that for a number of decision problems on graphs, polynomial-time algorithms |

Aug 14 | Friday13:00-13:30 | MF 11/12 | Willem Sonke | Power graph visualizations for event logs In many situations nowadays event logs are generated. Those logs contain structured inform |

Aug 14 | Friday10:00-10:30 | MF 11/12 | Chris Hoedemakers | Geometric Spanner Networks 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. |

Aug 17 | Monday14:00-14:30 | MF 3.122 | Luuk de Visser | Point-Feature Labelling in the 1-Slider Model: A Fixed-Parameter Tractable Algorithm 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 | Monday10:00-10:30 | MF 3.122 | Michel Cijsouw | Embedding Travel Time Cues in Schematic Maps 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. |

**Quartile 3:Time: Thursday 11:30-12:00**

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

Feb 5 | Thursday | MF 12 | Arthur van Goethem | On Streams and Incentives: A Synthesis of Individual and Collective Crowd Motion |

Feb 19 | Thursday | MF 12 | Tim Ophelders | The complexity of Snake |

Feb 26 | Thursday | MF 12 | Jasper Brekelmans | GlamMap: visualizing library metadata |

Mar 5 | Thursday11:00-13:00 | MF 12 | Quirijn Bouts Thom Castermans Tim Ophelders Willem Sonke | Practice talks EuroCG |

Mar 6 | Friday13:00-16:00 | MF 13 | Mark de Berg | Partition TreesLecture series |

Apr 2 | Thursday | MF 13 | Quirijn Bouts | TBA |

Apr 9 | Thursday | - | No seminar | TBA |

Apr 16 | Thursday | MF 3.119 | Kevin Verbeek | TBA |

**Quartile 2:Time: Monday 13:00-13:30**

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

Jan 5 | Monday | MF 2 | Ali Mehrabi | The intersection searching problem |

Jan 19 | Monday | MF 3.141 | Max Konzack | Visualizing Interactions in Trajectories |