10 papers
The Complexity of Stackelberg Pricing Games
Christoph Grüne, Dorothee Henke, Eva Rotenberg +1
We consider Stackelberg pricing games, which are also known as bilevel pricing problems, or combinatorial price-setting problems. This family of problems consists of games between…
Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
The element distinctness problem takes as input a list of values from a totally ordered universe and the goal is to decide whether contains any duplicates. It is a well…
Practical Insertion-Only Convex Hull
Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg
Convex hull data structures are fundamental in computational geometry. We study insertion-only data structures, supporting various containment and intersection queries. When is…
Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve
Sarita de Berg, Emil Toftegaard Gæde, Ivor van der Hoog +2
Range reporting is a classical problem in computational geometry. A (rectangular) reporting data structure stores a point set , such that, given a (rectangular) query region …
A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
For a planar point set , its convex hull is the smallest convex polygon that encloses all points in . The construction of the convex hull from an array containing i…
Fréchet Distance in Unweighted Planar Graphs
Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg +1
The Fréchet distance is a distance measure between trajectories in or walks in a graph . Given constant-time shortest path queries, the Discrete Fréchet distance $D_…