96 citations · 442 across the 64 of their papers we have counts for
6 papers · 1 filter
Counting Triangulations and other Crossing-free Structures via Onion Layers
Victor Alvarez, Karl Bringmann, Radu Curticapean +1
Let be a set of points in the plane. A crossing-free structure on is a plane graph with vertex set . Examples of crossing-free structures include triangulations of $…
A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations
Victor Alvarez, Karl Bringmann, Saurabh Ray
Let be a set of points. In this paper we show two new algorithms, one to compute the number of triangulations of , and one to compute the number of…
Balls into bins via local search: cover time and maximum load
Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer +1
We study a natural process for allocating m balls into n bins that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first…
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
Karl Bringmann, Christian Engels, Bodo Manthey +1
Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions…
Online Checkpointing with Improved Worst-Case Guarantees
Karl Bringmann, Benjamin Doerr, Adrian Neumann +1
In the online checkpointing problem, the task is to continuously maintain a set of k checkpoints that allow to rewind an ongoing computation faster than by a full restart. The only…
Bringing Order to Special Cases of Klee's Measure Problem
Karl Bringmann
Klee's Measure Problem (KMP) asks for the volume of the union of n axis-aligned boxes in d-space. Omitting logarithmic factors, the best algorithm has runtime O*(n^{d/2}) [Overmars…