Paul Seiferth

activity

20132021

most citedDynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

19 citations · 63 across the 10 of their papers we have counts for

collaborators

12 papers

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.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.CG2018★ 13 cited

Stabbing Pairwise Intersecting Disks by Five Points

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer +4

Suppose we are given a set $D$ of $n$ pairwise intersecting disks in the plane. A planar point set $P$ stabs $D$ if and only if each disk in $D$ conta…

cs.CG2017

Improved Time-Space Trade-offs for Computing Voronoi Diagrams

Bahareh Banyassady, Matias Korman, Wolfgang Mulzer +4

Let $P$ be a planar set of $n$ sites in general position. For $k \in {1, \dots, n - 1}$ , the Voronoi diagram of order $k$ for $P$ is obtained by subdividing the plane into cells such t…

cs.CG2017★ 5 cited

Routing in Polygonal Domains

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman +7

We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes. We may preprocess $P$ to obtain a label and…

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.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…

cs.CG2015★ 11 cited

Routing in Unit Disk Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1

Let $S \subset R^{2}$ be a set of $n$ sites. The unit disk graph $UD (S)$ on $S$ has vertex set $S$ and an edge between two distinct sites $s, t \in S$ if and only if $…

cs.CG2015★ 7 cited

Time-Space Trade-offs for Triangulations and Voronoi Diagrams

Matias Korman, Wolfgang Mulzer, Andre van Renssen +3

Let $S$ be a planar $n$ -point set. A triangulation for $S$ is a maximal plane straight-line graph with vertex set $S$ . The Voronoi diagram for $S$ is the subdivision of the plane i…

cs.CG2014

Approximate k-flat Nearest Neighbor Search

Wolfgang Mulzer, Huy L. Nguyen, Paul Seiferth +1

Let $k$ be a nonnegative integer. In the approximate $k$ -flat nearest neighbor ( $k$ -ANN) problem, we are given a set $P \subset R^{d}$ of $n$ points in $d$ -dimensional space…

cs.CG2013

Greedy is as Good as Delaunay (Almost)

Wolfgang Mulzer, Paul Seiferth

Let S be a planar point set. Krznaric and Levcopoulos proved that given the Delaunay triangulation DT(S) for S, one can find the greedy triangulation GT(S) in linear time. We provi…