182 citations · 515 across the 59 of their papers we have counts for
4 papers · 1 filter
Memory-Constrained Algorithms for Simple Polygons
Tetsuo Asano, Kevin Buchin, Maike Buchin +4
A constant-workspace algorithm has read-only access to an input array and may use only O(1) additional words of bits, where is the size of the input. We assume that…
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Wolfgang Mulzer, Daniel Werner
Let P be a d-dimensional n-point set. A Tverberg-partition of P is a partition of P into r sets P_1, ..., P_r such that the convex hulls conv(P_1), ..., conv(P_r) have non-empty in…
A Static Optimality Transformation with Applications to Planar Point Location
John Iacono, Wolfgang Mulzer
Over the last decade, there have been several data structures that, given a planar subdivision and a probability distribution over the plane, provide a way for answering point loca…
Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing
Esther Ezra, Wolfgang Mulzer
Motivated by the desire to cope with data imprecision, we study methods for taking advantage of preliminary information about point sets in order to speed up the computation of cer…