182 citations · 515 across the 59 of their papers we have counts for
6 papers · 2 filters
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…
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-…
A Lower Bound for Shallow Partitions
Wolfgang Mulzer, Daniel Werner
Let P be a planar n-point set. A k-partition of P is a subdivision of P into n/k parts of roughly equal size and a sequence of triangles such that each part is contained in a trian…