The Fréchet distance is arguably the most popular similarity measure for curves in computational geometry. It was first studied from an algorithmic perspective in 1991 by Helmut Alt and Michael Godau and has received considerable attention since then. In this talk I will outline some notable results in this line of research and end with some open problems.

We study the problem of approximating the discrete Fréchet distance between two 1-dimensional polygonal curves when the complexities of the two curves is imbalanced. We present a $2$-approximation algorithm with almost optimal running time. Further, in the extended version we show that this approximation factor is optimal and this result cannot be extended to higher dimensions unless the Orthogonal Vectors Hypothesis fails.

We consider colored variants of a class of geometric-combinatorial questions on $k$-gons and empty $k$-gons that have been started around 1935 by Erdős and Szekeres. In our setting we have $n$ points in general position in the plane, each one colored either red or blue. A structure on $k$ points is a geometric graph where the edges are spanned by (some of) these points and is called monochromatic if all $k$ points have the same color. Already for $k=4$ there exist interesting open problems. Most prominently, it is still open whether for any sufficiently large bichromatic set there always exists a convex empty, monochromatic quadrilateral. In order to shed more light on the underlying geometry we study the existence of five different monochromatic structures that all use exactly 4 points of a bichromatic point set. We provide several improved lower and upper bounds on the smallest $n$ such that every bichromatic set of at least $n$ points contains (some of) those monochromatic structures.

We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known O(epsilon^{-2}log(nm)) bound for the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor (1+-epsilon). Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet, q-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.

We study transforming one point set $A$ to an equal-size point set $B$ optimally, where translating any of a predefined set of groups of points incurs a cost independent of its size. We consider two objectives: minimizing the number of groups moved (Cardinality) and minimizing the total translation length of the groups (Length). When a matching between $A$ and $B$ is given -- that is, we know which point moves to which other point -- we prove that minimizing Cardinality is NP-hard in general, but efficiently solvable when the given groups form a hierarchy. Without a prescribed matching, we prove that both minimizing Cardinality and Length is NP-hard.

The Fréchet distance is a common similarity measure for curves (including polylines, trajectories, and walks in graphs). The Fréchet distance F_G(P,Q) between two walks P and Q in a graph G can be computed in time quadratic in the input size. Van der Hoog, van der Horst, Rotenberg, and Wulf [ESA'25] showed that this quadratic running time is likely unavoidable: Unless the Orthogonal Vectors Hypothesis fails, there is no strongly subquadratic-time 1.25-approximation algorithm for the Fréchet distance between two simple paths in an unweighted planar graph. They obtain positive results by imposing additional structure on the underlying graph. Specifically, if G is a regular planar tiling and P and Q are paths in G, then F_G(P,Q) can be computed in time O((|P|+|Q|)^{1.5}). We generalise this result to (1+ε)-approximations in d-dimensional grid graphs. In particular, we present an (1+ε)-approximate algorithm of F_G(P,Q) with runtime Õ(|Q|(|P|)^{1-2/d} ε^{-3}).

We are given access to a set of points in the plane through an oracle that returns the number of points contained in a given query rectangle. Our goal is to design algorithms that solve geometric extent problems using a small number of oracle queries. We present near-optimal algorithms for several fundamental problems, including the computation of the width, diameter, farthest neighbor, and minimum enclosing ball.

We study approximating the continuous Fréchet distance of two curves with complexity $n$ and $m$, under the assumption that only one of the two curves is $c$-packed. We show a simple technique to compute a $(1+\varepsilon)$-approximation in $\mathbb{R}^d$ in time $O(c\,\frac{n+m}{\varepsilon}\log\frac{n+m}{\varepsilon})$ when one of the curves is $c$-packed. Our approach is not only simpler than previous work, but also significantly improves the dependencies on $c$, $\varepsilon$, and $d$ (which is only linear). Moreover, it almost matches the asymptotically tight bound for when both curves are $c$-packed. Our algorithm is robust in the sense that it does not require knowledge of $c$, nor information about which of the two input curves is $c$-packed.

We aim to measure the mixedness of bichromatic point sets. The degree of mixedness is usually defined as the opposite of being well-separated. However, for very mixed point sets, typical measures of being well-separated no longer correspond to intuition. Therefore, we explore possible measures that address mixedness directly. Even in one dimension, many natural options arise. We study their properties and argue that they can behave rather different when applied to the same input. We also discuss the problem of transforming a given bichromatic point set into a `perfectly mixed' one, using as few operations as possible. If the operation is deletion, we show that a linear time algorithm exists to compute an optimal solution.

To analyze time-varying terrains efficiently, one generally needs an abstraction as well as a method to compare and match them over time. In this paper we consider merge trees as the method of abstraction, and the interleaving distance as a method to match and compare them. The interleaving distance is defined in terms of interleavings, which is a pair of maps between two merge trees. Due to the bottleneck nature of the interleaving distance, these maps fail to capture local similarities between the trees. In this paper we hence propose a notion of local optimality for interleavings. We give a constructive proof that a locally correct interleaving always exists.

We study the problem of covering a set of points in the plane with pairwise disjoint open unit disks. Let $k$ denote the smallest number of points for which there exists a configuration that cannot be covered. It is known that $k \ge 13$. A floating-point-based computer search by Aloupis et al. reported a 45-point configuration that appears not to be coverable, suggesting $k \leq 45$, but leaving a fully rigorous proof open. In this paper, we prove $k \le 44$ by presenting a 44-point configuration that cannot be covered by pairwise disjoint open unit disks. Our proof is computer-assisted but exact: we scale the input coordinates to integers and verify non-coverability using exact arithmetic (without floating-point computations). The verification proceeds in two stages: (i) enumerate candidate point-to-disk assignments via exact-cover enumeration, and (ii) for each assignment, determine feasibility by maintaining axis-aligned rectangles for disk centers and applying recursive subdivision with conservative geometric pruning. This yields a rigorous computer-assisted proof independent of floating-point tolerances.

The interleaving distance is a key tool for comparing merge trees, which provide topological summaries of scalar functions. In this work, we define an average merge tree for a pair of merge trees using the interleaving distance. Since such an average is not unique, we propose a method to construct a representative average merge tree. We further prove that the resulting merge tree indeed satisfies a natural notion of averaging for the two given merge trees. To demonstrate the structure of the average merge tree, we include illustrative examples.

A common sensing problem is to use a set of stationary tracking locations to monitor a collection of moving devices: Given n objects that need to be tracked, each following its own trajectory, and m stationary traffic control stations, each with a sensing region of adjustable range; how should we adjust the individual sensor ranges in order to optimize energy consumption? We present an algorithm based on geometric insights that is able to find optimal solutions for the min-max variant of the problem, which aims at minimizing peak power consumption. Instances with 500 moving objects and 25 stations can be solved in the order of seconds for scenarios that take minutes to play out in the real world, demonstrating real-time capability of our methods.

We study the fine-grained complexity of the $L_\infty$ Hausdorff distance under translation problem. Given two sets $P$ and $Q$ of $n$ and $m$ points, respectively, in $R^d$, we ask: How is the running time influenced by the dimension $d$, the relationship between $n$ and $m$, and whether we use the directed or undirected Hausdorff distance? We obtain, among other results, the following findings: - The directed Hausdorff distance has an intrinsically asymmetric time complexity: While the $\tilde O((nm)^{d/2})$ combinatorial lower bound for $d\ge 3$ of (Chan, SoCG'23) is conditionally tight when $m \leq n$, we show that this is not the case for $n \ll m$ by providing a combinatorial, almost-linear-time algorithm for $d=3$ and $n=m^{o(1)}$. - We further prove general, i.e., non-combinatorial, conditional lower bounds, in particular: (1) $m^{\lfloor d/2 \rfloor -o(1)}$ for $d \geq 3$ and small $n$ and (2) $n^{ d/2 -o(1)}$ for $d=3$ and small $m$. - We observe that the directed and undirected case is closely related, in particular, most lower bounds for $d \geq 3$ hold for both the directed and undirected variant. A remarkable exception is the case of $d=1$ for which we provide a conditional separation.

We study the APX-hard problem of covering a polygon with a minimum number of triangles, which is known to be $\exists\mathbb R$-complete, even for polygons without holes and vertices in general position. For the special case partitions, we argue that a triangulation yields a 3-approximation. Our main result is a 10-approximation for computing a minimum triangle cover in polygons without holes.

The weak graph distance is a distance measure for immersed graphs which is NP-complete to decide. We present a new XP-time approach to decide it, based on vertices that we can initially disregard.

While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in $\Omega(n / \log n)$, where $n$ denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial $n$-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least $n$. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness $0$), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than $n$. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in $\Omega(n / \log n)$ for strip packing, and there exist online algorithms with competitive ratios in $O(1)$ for perimeter packing, or in $O(\sqrt{n})$ for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).

In 1984, Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves. His conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hamilton cycle. In this work, we construct counterexamples to Winkler's conjecture for all n >= 6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n=6 curves (even their number was not previously known), among which we found 72 counterexamples. We also construct monotone Venn diagrams, i.e., diagrams that can be drawn with n convex curves, and are not extendable, for all n >= 7. We also disprove another conjecture about the Hamiltonicity of the (primal) graph of a Venn diagram. Specifically, while working on Winkler's conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n >= 4.

To understand the geometry of a graph $G$ embedded on a closed surface, an interesting tool is the number of intersection of $G$ with any closed curve $c$. A useful map is the length spectrum $\mu_G(c)$ counting the minimum number of intersections between G and any curve freely homotopic to $c$. The notion of kernel have been introduced by Schrijver in the 90’s. It corresponds to an embedded graph $G$ such that for any proper minor $H$ of $G$, $\mu_H<\mu_G$. It is quite obvious that any embedded graph $G$ has a minor $K$ which is a kernel and with same length spectrum. Such a minor is called a minor kernel. In this talk, I describe an algorithm to compute a minor kernel of a given graph in $O(n^3\log n)$. Thanks to a correspondence with system of curves, this algorithm relies on a tight bound on the length of minimal bigon in system of curves. As a consequence of the computation of minor kernel, we are able to decide whether two graphs minors have the same spectrum and improve the state-of-the-art algorithm to compute $\mu_G(c)$.

An n-Venn diagram is a diagram in the plane consisting of n simple closed curves that intersect only finitely many times such that each of the 2^n possible intersections is represented by a single connected region. An n-Venn diagram has at most 2^n-2 crossings, and if this maximum number of crossings is attained, then only two curves intersect in every crossing. To complement this, Bultena and Ruskey considered n-Venn diagrams that minimize the number of crossings, which implies that many curves intersect in every crossing. Specifically, they proved that the total number of crossings in any n-Venn diagram is at least $L_n\ass\lceil\frac{2^n-2}{n-1}\rceil$. Diagrams achieving this bound are called minimum Venn diagrams, and are known only for n<=7. Bultena and Ruskey conjectured that they exist for all n>= 8. In this work, we establish an asymptotic version of their conjecture, obtaining n-Venn diagrams with (1+o(1))L_n crossings when n is a power of 2, and n-Venn diagrams with (2+o(1))L_n crossings in general. Our constructions are based on partitions of the hypercube into isometric paths and cycles, using a result of Ramras.

We propose an alternative formulation of the well-known Hough transform to detect lines in point clouds. Replacing the discretized voting scheme of the classical Hough transform by a continuous score function, its persistent features in the sense of persistent homology give a set of candidate lines. We also devise and implement an algorithm to efficiently compute these candidate lines.

A connected topological drawing of a graph divides the plane into a number of cells. The type of a cell c is the cyclic sequence of crossings and vertices along the boundary walk of c. For example, all triangular cells with three incident crossings and no incident vertex share the same cell type. In this work, we initiate the in-depth study of drawings that do not contain one fixed cell type, and investigate the edge density of the corresponding graph classes.

The verbose persistent homology transform (VPHT) is a topological summary of shapes in Euclidean space. Assuming general position, the VPHT is injective, meaning shapes can be reconstructed using only the VPHT. In this work, we investigate cases in which the VPHT is not injective, focusing on a simple setting of degeneracy; graphs whose vertices are all collinear. We identify both necessary properties and sufficient properties for non-reconstructibility of such graphs, bringing us closer to a complete classification.

Given a simple drawing of a graph, a sub-drawing of a plane cycle of length k induces two connected regions of the plane. If one of the two regions does not contain any of the remaining vertices of the drawing, we call the cycle an empty plane k-cycle. In this work, we examine simple drawings of the complete graph K_n with respect to the existence of empty plane k-cycles for small k. We show that every vertex in a simple drawing of K_n is incident to an empty plane k-cycle with k=5 or k=6.

The Persistent Homology Transform (PHT) has emerged as a powerful topological summary for shape analysis, capturing multiscale geometric information by scanning a shape along all possible directions. In this paper we study a close variant namely the Radial Persistence Transform (RPT). The RPT maps a point $x$ in the ambient space to the persistence diagram of the squared Euclidean distance function $d_\mathbb{E}^2 (\cdot , x) |_{\M}$ restricted to a manifold $\mathcal{M}$. Results by e.g. Bruce, Giblin, and Gibson and Porteous establish that the topology of this distance function, and hence the persistence diagram, undergoes changes if $x$ traverses the symmetry set and focal set. We present an interactive web-based 2D tool, Bouquet2D, designed to explore these transitions through the lens of vineyards. By parameterizing $x$ along a user-defined loop $\gamma$, our tool tracks the continuous evolution of persistence diagrams, revealing the complex ``braiding'' patterns and monodromy in the vineyard recently characterized by Chambers et al. [SODA 26]. The tool features a real-time spline-based interface, allowing researchers to deform $\M$ and observe how geometric bifurcations manifest as topological events in the vineyard. By exhibiting the relation between the symmetry and focal set and the topology of the vineyard, this software provides a visual framework for investigating the origin of topology in vineyards.

This paper considers the task of connecting points on a piece of paper by drawing a curve between each pair of them. Under mild assumptions, we prove that many pairwise disjoint curves are unavoidable if either of the following rules is obeyed: any two adjacent curves do not cross, or any two non-adjacent curves cross at most once. On the other hand, we demonstrate how to draw all curves such that any two adjacent curves cross exactly once, any two non-adjacent curves cross at least once and at most twice, and thus no two curves are disjoint. Furthermore, we analyze the emergence of disjoint curves without these mild assumptions, and characterize the plane structures in complete graph drawings guaranteed by each of the rules above.