13 citations · 26 across the 20 of their papers we have counts for
6 papers · 1 filter
Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs
Ivor van der Hoog, André Nusser, Eva Rotenberg +1
A classical problem in computational geometry and graph algorithms is: given a dynamic set S of geometric shapes in the plane, efficiently maintain the connectivity of the intersec…
Robust Classification of Dynamic Bichromatic point Sets in R2
Erwin Glazenburg, Frank Staals, Marc van Kreveld
Let be a set of points in , and let . Our goal is to compute a line that "best" separates the "red" points from the "blue" points w…
Fine-Grained Complexity of Earth Mover's Distance under Translation
Karl Bringmann, Frank Staals, Karol Węgrzycki +1
The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two poin…
The Complexity of Geodesic Spanners using Steiner Points
Sarita de Berg, Tim Ophelders, Irene Parada +2
A geometric -spanner on a set of point sites in a metric space is a subgraph of the complete graph on such that for every pair of sites the d…
Exact solutions to the Weighted Region Problem
Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira +1
In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region…
Robust Bichromatic Classification using Two Lines
Erwin Glazenburg, Thijs van der Horst, Tom Peters +2
Given two sets and of points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in from the "bl…