1 citations · 2 across the 15 of their papers we have counts for
20 papers · 1 filter
Simulated Annealing for Antenna Placements
Mikkel Abrahamsen, Jacobus Conradi, Asbjørn Lind
The 2026 ACM SIGSPATIAL GIS Cup posed the following geometric challenge: Given a set of simple, pair-wise disjoint polygons, compute antennas (points) on polygon boundaries, ma…
A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane
Sarita de Berg, Jacobus Conradi, Peter Kramer +2
The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through th…
Computing All Optimal Partial -Wasserstein Matchings on the Line
Sebastian Angrick, Jacobus Conradi, Mónika Csikós +5
For , the -Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p…
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…
Tight Fréchet bounds for -low density curves
Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl +1
The Fréchet distance is a well-studied similarity measure between curves. We computing the Fréchet distance between -low-density curves, the most general of realistic curve assu…
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…
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…
Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin +4
A fundamental problem in shape matching and geometric similarity is computing the maximum area overlap between two polygons under translation. For general simple polygons, the best…
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…
Simpler and Faster Contiguous Art Gallery
Sarita de Berg, Jacobus Conradi, Ivor van der Hoog +1
The contiguous art gallery problem was introduced at SoCG'25 in a merged paper that combined three simultaneous results, each achieving a polynomial-time algorithm for the problem.…
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{-…
Computing Non-Obtuse Triangulations with Few Steiner Points
Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi +2
We present the winning implementation of the Seventh Computational Geometry Challenge (CG:SHOP 2025). The task in this challenge was to find non-obtuse triangulations for given pla…
Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better
Jacobus Conradi, Anne Driemel
Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation…
Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D
Lotte Blank, Jacobus Conradi, Anne Driemel +3
The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the sim…
Revisiting the Fréchet distance between piecewise smooth curves
Jacobus Conradi, Anne Driemel, Benedikt Kolbe
Since its introduction to computational geometry by Alt and Godau in 1992, the Fréchet distance has been a mainstay of algorithmic research on curve similarity computations. The fo…
Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warping
Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros +1
We present algorithms for the computation of -coresets for -median clustering of point sequences in under the -dynamic time warping (DTW) distance…
Finding Complex Patterns in Trajectory Data via Geometric Set Cover
Jacobus Conradi, Anne Driemel
Clustering trajectories is a central challenge when faced with large amounts of movement data such as GPS data. We study a clustering problem that can be stated as a geometric set…
-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension
Jacobus Conradi, Anne Driemel, Benedikt Kolbe
We consider the -Approximate Nearest Neighbour (ANN) Problem for polygonal curves in -dimensional space under the Fréchet distance and ask to what extent known…
Faster Approximate Covering of Subcurves under the Fréchet Distance
Frederik Brüning, Jacobus Conradi, Anne Driemel
Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are…
On Computing the -Shortcut Fréchet Distance
Jacobus Conradi, Anne Driemel
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijection…