12 papers
The Contiguous Art Gallery Problem is in Î(n log n)
Sarita de Berg, Jacobus Conradi, Ivor van der Hoog +1
Recently, a natural variant of the Art Gallery problem, known as the \emph{Contiguous Art Gallery problem} was proposed. Given a simple polygon , the goal is to partition its bo…
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 com…
Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl +1
The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in t…
On Small Pair Decompositions for Point Sets
Kevin Buchin, Jacobus Conradi, Sariel Har-Peled +5
$\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algo…
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{…
On computing the (exact) Fréchet distance with a frog
Jacobus Conradi, Ivor van der Hoog, Eva Rotenberg
The continuous Frechet distance between two polygonal curves is classically computed by exploring their free space diagram. Recently, Har-Peled, Raichel, and Robson [SoCG'25] propo…