7 papers · 1 filter
Flips in Odd Matchings
Oswin Aichholzer, Anna Brötzner, Daniel Perz +1
Let be a set of points in the plane in general position. We define the graph whose vertex set is the set of all plane matchings on $\mathcal…
Unfairly Splitting Separable Necklaces
Patrick Schnider, Linus Stalder, Simon Weber
The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-kno…
AuToMATo: An Out-Of-The-Box Persistence-Based Clustering Algorithm
Marius Huber, Sara Kalisnik, Patrick Schnider
We present AuToMATo, a novel clustering algorithm based on persistent homology. While AuToMATo is not parameter-free per se, we provide default choices for its parameters that make…
Connected Matchings
Oswin Aichholzer, Sergio Cabello, Viola Mészáros +2
We show that each set of points in the plane in general position has a straight-line matching with at least edges whose segments form a connected set, and such…
Barking dogs: A Fréchet distance variant for detour detection
Ivor van der Hoog, Fabian Klute, Irene Parada +1
Imagine you are a dog behind a fence and a hiker is passing by at constant speed along the hiking path . In order to fulfil your duties as a watchdog, you desire to bark as…
Computing Enclosing Depth
Bernd Gärtner, Fatime Rasiti, Patrick Schnider
Enclosing depth is a recently introduced depth measure which gives a lower bound to many depth measures studied in the literature. So far, enclosing depth has only been studied fro…
Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
Michaela Borzechowski, John Fearnley, Spencer Gordon +3
We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sin…