5 papers · 1 filter
Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen +3
In the imprecise geometry model, the input is an imprecise point set, which is a family of regions , where for each one may retrieve the true point $p_…
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…
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…
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…
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…