Lotte Blank

activity

20242026

most citedFine-Grained Complexity of Continuous Euclidean k-Center

1 citations · 1 across the 3 of their papers we have counts for

collaborators

8 papers

cs.CG2026

The Quick Dog Jumps the Log

Lotte Blank, Anne Driemel, Sariel Har-Peled +1

We give linear-time, and thus optimal, $(1 + ε)$ -approximation algorithms for numerous variants of the Frechet distance between $c$ -packed curves (where $c \in O (1)$ ), remo…

cs.CG2026★ 1 cited

Fine-Grained Complexity of Continuous Euclidean k-Center

Lotte Blank, Karl Bringmann, Parinya Chalermsook +4

In the (continuous) Euclidean $k$ -center problem, given $n$ points in $R^{d}$ and an integer $k$ , the goal is to find $k$ center points in $R^{d}$ that minimize the m…

cs.CG2026

Fréchet Distance in the Imbalanced Case

Lotte Blank

Given two polygonal curves $P$ and $Q$ defined by $n$ and $m$ vertices with $m \leq n$ , we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of $2…

cs.DS2025

The Expiration Streaming Model: Diameter, $k$ -Center, Counting, Sampling, and Friends

Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi +5

An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where eac…

cs.CG2025

Bicriteria Polygon Aggregation with Arbitrary Shapes

Lotte Blank, David Eppstein, Jan-Henrik Haunert +6

We study the problem of aggregating a set of polygons by covering them with disjoint representative regions, thereby inducing a clustering of the polygons. Equivalently, this can b…

cs.CG2025

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…

cs.CG2024

A faster algorithm for the Fréchet distance in 1D for the imbalanced case

Lotte Blank, Anne Driemel

The fine-grained complexity of computing the Fréchet distance has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from…