W. Mulzer

activity

20062025

most citedMinimum-weight triangulation is NP-hard

182 citations · 515 across the 59 of their papers we have counts for

collaborators

Showing 2016Show all

6 papers · 1 filter

cs.CG2016

The Rainbow at the End of the Line --- A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles +1

Let $C_{1}, ..., C_{d + 1}$ be $d + 1$ point sets in $R^{d}$ , each containing the origin in its convex hull. A subset $C$ of $⋃_{i = 1}^{d + 1} C_{i}$ is called a colorful choice (o…

cs.CG2016★ 19 cited

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +2

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $L_{p}$ -norms and additively…

cs.IT2016★ 4 cited

Encoding Arguments

Pat Morin, Wolfgang Mulzer, Tommy Reddad

Many proofs in discrete mathematics and theoretical computer science are based on the probabilistic method. To prove the existence of a good object, we pick a random object and sho…

cs.CG2016★ 11 cited

A Time-Space Trade-off for Computing the k-Visibility Region of a Point in a Polygon

Yeganeh Bahoo, Bahareh Banyassady, Prosenjit Bose +2

Let $P$ be a simple polygon with $n$ vertices, and let $q \in P$ be a point in $P$ . Let $k \in {0, \dots, n - 1}$ . A point $p \in P$ is $k$ -visible from $q$ if and only if the li…

cs.CG2016★ 5 cited

Spanners for Directed Transmission Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1

Let $P \subset R^{2}$ be a planar $n$ -point set such that each point $p \in P$ has an associated radius $r_{p} > 0$ . The transmission graph $G$ for $P$ is the directed graph w…

cs.CG2016★ 1 cited

Reachability Oracles for Directed Transmission Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1

Let $P \subset R^{d}$ be a set of $n$ points in $d$ dimensions such that each point $p \in P$ has an associated radius $r_{p} > 0$ . The transmission graph $G$ for $P$ is the d…