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 cs.CGShow all

60 papers · 1 filter

cs.CG2025

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4

A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…

cs.CG2024

Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs

Katharina Klost, Wolfgang Mulzer

We describe optimal robust algorithms for finding a triangle and the unweighted girth in a unit disk graph, as well as finding a triangle in a transmission graph.In the robust sett…

cs.CG2023

Insertion-Only Dynamic Connectivity in General Disk Graphs

Haim Kaplan, Katharina Klost, Kristin Knorr +2

Let $S \subseteq R^{2}$ be a set of $n$ \emph{sites} in the plane, so that every site $s \in S$ has an \emph{associated radius} $r_{s} > 0$ . Let $D (S)$ be the \emph{disk inter…

cs.CG2022

Well-Separation and Hyperplane Transversals in High Dimensions

Helena Bergold, Daniel Bertschinger, Nicolas Grelier +2

A family of $k$ point sets in $d$ dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong ass…

cs.CG2022

Nearest-Neighbor Decompositions of Drawings

Jonas Cleve, Nicolas Grelier, Kristin Knorr +3

Let $D$ be a set of straight-line segments in the plane, potentially crossing, and let $c$ be a positive integer. We denote by $P$ the union of the endpoints of the strai…

cs.CG2022

Unique Sink Orientations of Grids is in Unique End of Potential Line

Michaela Borzechowski, Wolfgang Mulzer

The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. UEOPL captures search problems where the instan…

cs.CG2022★ 1 cited

Flipping Plane Spanning Paths

Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer +3

Let $S$ be a planar point set in general position, and let $P (S)$ be the set of all plane straight-line paths with vertex set $S$ . A flip on a path $P \in P (S)$ …

cs.CG2021★ 2 cited

Dynamic Connectivity in Disk Graphs

Alexander Baumann, Haim Kaplan, Katharina Klost +4

Let $S$ be a set of $n$ sites in the plane, so that every site $s \in S$ has an associated radius $r_{s} > 0$ . Let $D (S)$ be the disk intersection graph defined by $S$ , i.e…

cs.CG2021

Long Plane Trees

Sergio Cabello, Michael Hoffmann, Katharina Klost +2

In the longest plane spanning tree problem, we are given a finite planar point set $P$ , and our task is to find a plane (i.e., noncrossing) spanning tree for $\mathcal{P}…

cs.CG2020

Minimum Cuts in Geometric Intersection Graphs

Sergio Cabello, Wolfgang Mulzer

Let $D$ be a set of $n$ disks in the plane. The disk graph $G_{D}$ for $D$ is the undirected graph with vertex set $D$ in which two disks are…

cs.CG2020★ 1 cited

A Simple Randomized $O (n lo g n)$ --Time Closest-Pair Algorithm in Doubling Metrics

Anil Maheshwari, Wolfgang Mulzer, Michiel Smid

Consider a metric space $(P, d i s t)$ with $N$ points whose doubling dimension is a constant. We present a simple, randomized, and recursive algorithm that computes, in $O (N lo g N)$ …

cs.CG2020

Long Alternating Paths Exist

Wolfgang Mulzer, Pavel Valtr

Let $P$ be a set of $2 n$ points in convex position, such that $n$ points are colored red and $n$ points are colored blue. A non-crossing alternating path on $P$ of length $ℓ$ is…

cs.CG2020

Computational Complexity of the $α$ -Ham-Sandwich Problem

Man-Kwun Chiu, Aruni Choudhary, Wolfgang Mulzer

The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $R^{d}$ , there is a hyperplane that bisects them simultaneously. An extension by Bárány, Hubard,…

cs.CG2020★ 1 cited

Routing in Unit Disk Graphs without Dynamic Headers

Wolfgang Mulzer, Max Willert

Let $V \subset R^{2}$ be a set of $n$ sites in the plane. The unit disk graph $D G (V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if an…

cs.CG2020★ 1 cited

The Tree Stabbing Number is not Monotone

Wolfgang Mulzer, Johannes Obenaus

Let $P \subseteq R^{2}$ be a set of points and $T$ be a spanning tree of $P$ . The \emph{stabbing number} of $T$ is the maximum number of intersections any line in the plane…

cs.CG2019

Maximum Matchings in Geometric Intersection Graphs

Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer

Let $G$ be an intersection graph of $n$ geometric objects in the plane. We show that a maximum matching in $G$ can be found in $O (ρ^{3 ω /2} n^{ω /2})$ time with high probability, wher…

cs.CG2019

Triangles and Girth in Disk Graphs and Transmission Graphs

Haim Kaplan, Katharina Klost, Wolfgang Mulzer +3

Let $S \subset R^{2}$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_{s} > 0$ . The disk graph $D (S)$ is the undirected graph with vertex set $S$ and a…

cs.CG2019★ 2 cited

No-dimensional Tverberg Theorems and Algorithms

Aruni Choudhary, Wolfgang Mulzer

Tverberg's theorem states that for any $k \geq 2$ and any set $P \subset R^{d}$ of at least $(d + 1) (k - 1) + 1$ points in $d$ dimensions, we can partition $P$ into $k$ subse…

cs.CG2019

On the Stretch Factor of Polygonal Chains

Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer +1

Let $P = (p_{1}, p_{2}, \dots, p_{n})$ be a polygonal chain in $R^{d}$ . The stretch factor of $P$ is the ratio between the total length of $P$ and the distance of its endpoints, $\s…

cs.CG2019

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…

cs.CG2019★ 1 cited

Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead

Pankaj K. Agarwal, Ravid Cohen, Dan Halperin +1

We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main resu…

cs.CG2019★ 1 cited

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 $O (lo g^{2} n)$ update time and $O (lo g n)$ vertical ray shooting…

cs.CG2019

Routing in Histograms

Man-Kwun Chiu, Jonas Cleve, Katharina Klost +5

Let $P$ be an $x$ -monotone orthogonal polygon with $n$ vertices. We call $P$ a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizonta…

cs.CG2018

Approximate Minimum-Weight Matching with Outliers under Translation

Pankaj K. Agarwal, Haim Kaplan, Geva Kipper +4

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a tran…

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs

Insertion-Only Dynamic Connectivity in General Disk Graphs

Well-Separation and Hyperplane Transversals in High Dimensions

Nearest-Neighbor Decompositions of Drawings

Unique Sink Orientations of Grids is in Unique End of Potential Line

Flipping Plane Spanning Paths

Dynamic Connectivity in Disk Graphs

Long Plane Trees

Minimum Cuts in Geometric Intersection Graphs

A Simple Randomized O(nlogn)--Time Closest-Pair Algorithm in Doubling Metrics

Long Alternating Paths Exist

Computational Complexity of the α-Ham-Sandwich Problem

Routing in Unit Disk Graphs without Dynamic Headers

The Tree Stabbing Number is not Monotone

Maximum Matchings in Geometric Intersection Graphs

Triangles and Girth in Disk Graphs and Transmission Graphs

No-dimensional Tverberg Theorems and Algorithms

On the Stretch Factor of Polygonal Chains

An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model

Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead

Dynamic Maintenance of the Lower Envelope of Pseudo-Lines

Routing in Histograms

Approximate Minimum-Weight Matching with Outliers under Translation

A Simple Randomized $O (n lo g n)$ --Time Closest-Pair Algorithm in Doubling Metrics

Computational Complexity of the $α$ -Ham-Sandwich Problem