1 citations · 3 across the 8 of their papers we have counts for
6 papers · 1 filter
Minimal Representations of Order Types by Geometric Graphs
Oswin Aichholzer, Martin Balko, Michael Hoffmann +8
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order ty…
Triangles and Girth in Disk Graphs and Transmission Graphs
Haim Kaplan, Katharina Klost, Wolfgang Mulzer +3
Let be a set of sites, where each has an associated radius . The disk graph is the undirected graph with vertex set and a…
A Constructive Proof of a Concentration Bound for Real-Valued Random Variables
Wolfgang Mulzer, Natalia Shenkman
Almost 10 years ago, Impagliazzo and Kabanets (2010) gave a new combinatorial proof of Chernoff's bound for sums of bounded independent random variables. Unlike previous methods, t…
An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model
Jonas Cleve, Wolfgang Mulzer
We perform an experimental evaluation of algorithms for finding geodesic shortest paths between two points inside a simple polygon in the constant-workspace model. In this model, t…
Dynamic Maintenance of the Lower Envelope of Pseudo-Lines
Pankaj K. Agarwal, Ravid Cohen, Dan Halperin +1
We present a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines. The structure has update time and vertical ray shooting…
Routing in Histograms
Man-Kwun Chiu, Jonas Cleve, Katharina Klost +5
Let be an -monotone orthogonal polygon with vertices. We call a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizonta…