BARC talk by Jacobus Conradi

Title:
On Algorithms and Lower Bounds for Polygon Containment and Polygon Overlap

Abstract:
We study the problem of deciding whether one polygon can be translated into another and, more generally, of computing the maximum overlap between two polygons under translation. We present an improved algorithm that breaks a nearly 30-year-old barrier for rectilinear polygons.

Complementing our algorithmic results, we establish conditional lower bounds showing that, in some natural settings, the current state of the art is essentially optimal.

Bio:
Jacobus recently joined BARC. Before his Copenhagen-based adventures, he studied mathematics and computer science in Bonn, focusing on graph theory, geometry, and topology. He completed his PhD under the supervision of Anne Driemel, where he investigated similarity measures between geometric objects, particularly curves. He is especially interested in the interplay between theoretical algorithms and their practical feasibility.

During his PhD, Jacobus worked on classical problems such as clustering, nearest-neighbor data structures, and coresets in settings that highlight trade-offs between time and space. Within this broad area, he focused on models capturing realistic inputs, such as c-packed curves. His broader interests include art-gallery problems, packing problems, and, more generally, geometric problems with a strong emphasis on practicality.

Host:
Mikkel Vind Abrahamsen