6 citations · 6 across the 9 of their papers we have counts for
14 papers
Computing Planar Convex Hulls with a Promise
Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan +5
Computing the convex hull of a planar -point set is one of the most fundamental problems in computational geometry. It has an lower bound in the algebraic comp…
Engineering Fully Dynamic Convex Hulls
Ivor van der Hoog, Henrik Reinstädtler, Eva Rotenberg
We present a new fully dynamic algorithm for maintaining convex hulls under insertions and deletions while supporting geometric queries. Our approach combines the logarithmic metho…
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 …
Computing the Fréchet Distance When Just One Curve is -Packed: A Simple Almost-Tight Algorithm
Jacobus Conradi, Ivor van der Hoog, Thijs van der Horst +1
We study approximating the continuous Fréchet distance of two curves with complexity and , under the assumption that only one of the two curves is -packed. Driemel, Har{-…
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…
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…
Dynamic Indexing Through Learned Indices with Worst-case Guarantees
Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg +1
Indexing data is a fundamental problem in computer science. Recently, various papers apply machine learning to this problem. For a fixed integer , a \emph{learned inde…
Local Density and its Distributed Approximation
Aleksander Bjørn Christiansen, Ivor van der Hoog, Eva Rotenberg
The densest subgraph problem is a classic problem in combinatorial optimisation. Danisch, Chan, and Sozio propose a definition for \emph{local density} that assigns to each vertex…
Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs
Ivor van der Hoog, Irene Parada, Eva Rotenberg
A directed graph is upward planar if it admits a planar embedding such that each edge is -monotone. Unlike planarity testing, upward planarity testing is NP-hard except in r…
Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity
Jacob Holm, Ivor van der Hoog, Eva Rotenberg
We study dynamic planar graphs with vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We d…
Efficient Fréchet distance queries for segments
Maike Buchin, Ivor van der Hoog, Tim Ophelders +3
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve , such that for any query segment one can efficiently comp…
Smoothed Analysis of Order Types
Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik
Consider an ordered point set , its order type (denoted by ) is a map which assigns to every triple of points a value in based on whether the…