1 citations · 1 across the 9 of their papers we have counts for
6 papers · 1 filter
Tight Adaptive Bounds for Convex Hulls
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Adaptive sorting algorithms exploit existing order in the input to obtain better-than-worst-case running times. A classical example is sorting by runs: if the input can be partitio…
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…
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…
Simpler Universally Optimal Dijkstra
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Let G be a weighted (directed) graph with n vertices and m edges. Given a source vertex s, Dijkstra's algorithm computes the shortest path lengths from s to all other vertices in O…
Instance-Optimal Imprecise Convex Hull
Sarita de Berg, Ivor van der Hoog, Eva Rotenberg +2
Imprecise measurements of a point set P = (p1, ..., pn) can be modelled by a family of regions F = (R1, ..., Rn), where each imprecise region Ri contains a unique point pi. A retri…
Efficient Greedy Discrete Subtrajectory Clustering
Ivor van der Hoog, Lara Ost, Eva Rotenberg +1
We cluster a set of trajectories T using subtrajectories of T. Clustering quality may be measured by the number of clusters, the number of vertices of T that are absent from the cl…