182 citations · 515 across the 59 of their papers we have counts for
7 papers · 1 filter
Self-improving Algorithms for Coordinate-Wise Maxima and Convex Hulls
Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri
Finding the coordinate-wise maxima and the convex hull of a planar point set are probably the most classic problems in computational geometry. We consider these problems in the sel…
Four Soviets Walk the Dog-Improved Bounds for Computing the Fréchet Distance
Kevin Buchin, Maike Buchin, Wouter Meulemans +1
Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Al…
Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
Oswin Aichholzer, Wolfgang Mulzer, Alexander Pilz
Let T be a triangulation of a simple polygon. A flip in T is the operation of removing one diagonal of T and adding a different one such that the resulting graph is again a triangu…
Data Structures on Event Graphs
Bernard Chazelle, Wolfgang Mulzer
We investigate the behavior of data structures when the input and operations are generated by an event graph. This model is inspired by Markov chains. We are given a fixed graph G,…
Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent
Maarten Löffler, Wolfgang Mulzer
We show that Delaunay triangulations and compressed quadtrees are equivalent structures. More precisely, we give two algorithms: the first computes a compressed quadtree for a plan…
Self-improving Algorithms for Coordinate-wise Maxima
Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri
Computing the coordinate-wise maxima of a planar point set is a classic and well-studied problem in computational geometry. We give an algorithm for this problem in the \emph{self-…