K. Bringmann

activity

20242026

most citedTight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling

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

collaborators

Showing cs.CGShow all

3 papers · 1 filter

cs.CG2026

Dynamic and Streaming Algorithms for Union Volume Estimation

Sujoy Bhore, Karl Bringmann, Timothy M. Chan +1

The union volume estimation problem asks to $(1 \pm ε)$ -approximate the volume of the union of $n$ given objects $X_{1}, \dots, X_{n} \subset R^{d}$ . In their seminal wor…

cs.CG2025

Polyline Simplification has Cubic Complexity

Karl Bringmann, Bhaskar Ray Chaudhury

In the classic polyline simplification problem we want to replace a given polygonal curve $P$ , consisting of $n$ vertices, by a subsequence $P^{'}$ of $k$ vertices from $P$ such that…

cs.CG2025

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation

Union volume estimation is a classical algorithmic problem. Given a family of objects $O_{1}, \dots, O_{n} \subseteq R^{d}$ , we want to approximate the volume of their union. In…