Refereed Conferences:

1. April 2017
   Bahareh Banyassady,
   Matias Korman,
   Wolfgang Mulzer,
   André van Renssen,
   Marcel Roeloffzen,
   Paul Seiferth, and
   Yannik Stein

   Improved Time-Space Trade-offs for Computing Voronoi Diagrams

   Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), Hannover, Germany, 2017

   [pdf]

   Abstract

   Let P be a planar n-point set in general position. For k in {1, . . . , n − 1}, the Voronoi diagram of order k is obtained by subdividing the plane into regions such that points in the same cell have the same set of nearest k neighbors in P. The (nearest point) Voronoi diagram (NVD) and the farthest point Voronoi diagram (FVD) are the particular cases of k = 1 and k = n − 1, respectively. It is known that the family of all higher-order Voronoi diagrams of order 1 to K for P can be computed in total time O(nK^2 + n log n) using O(K^2(n − K)) space. Also NVD and FVD can be computed in O(n log(n)) time using O(n) space.

   For s in {1, . . . , n}, an s-workspace algorithm has random access to a read-only array with the sites of P in arbitrary order. Additionally, the algorithm may use O(s) words of Theta(log (n)) bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards.

   We describe a deterministic s-workspace algorithm for computing an NVD and also an FVD for P that runs in O((n^2/s) log(s)) time. Moreover, we generalize our s-workspace algorithm for computing the family of all higher-order Voronoi diagrams of P up to order k = O(sqrt(s)) in total time O((n^2k^6/s)*log^(1+eps)(K)(log(s)/log(K))^O(1), for any fixed eps > 0. Previously, for Voronoi diagrams, the only known s-workspace algorithm was to find an NVD for P in expected time O((n^2/s) log(s) + n log s log^*(s)). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.

2. January 2017
   Haim Kaplan,
   Wolfgang Mulzer,
   Liam Roditty,
   Paul Seiferth, and
   Micha Sharir

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

   Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.

   [pdf] [arXiv] [slides]

   Abstract

   We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes L_p-norms and additively weighted Euclidean distances, and for general (convex, pairwise disjoint) sites that have constant description complexity (line segments, disks, etc.). Our data structure has a polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required O(n^eps) time for an update and O(log n) time for a query. Our data structure has numerous applications, and n all of them it gives faster algorithms, typically reducing an O(n^eps) factor in the bounds to polylogarithmic. To further demonstrate its power, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph.

   To obtain this data structure, we combine and extend various techniques and obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of "vertical" shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of an appropriate size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context). To analyze this algorithm, we improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan's algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in three dimensions. While doing this, we also revisit Chan's technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time.

3. April 2016
   Haim Kaplan,
   Wolfgang Mulzer,
   Liam Roditty, and
   Paul Seiferth

   Routing in Unit Disk Graphs

   Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico, 2016.

   [pdf] [arXiv] [slides]

   Abstract

   Let S be a set of n sites in the plane. 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 s and t have Euclidean distance |st| <= 1. A routing scheme R for UD(S) assigns to each site s in S a label l(s) and a routing table rho(s). For any two sites s,t in S, the scheme R must be able to route a packet from s to t in the following way: given a current site r (initially, r=s), a header h (initially empty), and the target label l(t), the scheme R may consult the current routing table rho(r) to compute a new site r′ and a new header h′, where r′ is a neighbor of r. The packet is then routed to r′, and the process is repeated until the packet reaches t. The resulting sequence of sites is called the routing path. The stretch of R is the maximum ratio of the (Euclidean) length of the routing path produced by R and the shortest path in UD(S), over all pairs of distinct sites in S.

   For any given eps>0, we show how to construct a routing scheme for UD(S) with stretch 1+eps using labels of O(logn) bits and routing tables of O(eps^-5 log^2(n) log^2(D)) bits, where D is the (Euclidean) diameter of UD(S). The header size is O(log(n)log(D)) bits.

4. March 2015
   Matias Korman,
   Wolfgang Mulzer,
   André van Renssen,
   Marcel Roeloffzen,
   Paul Seiferth, and
   Yannik Stein

   Time-Space Trade-offs for Triangulations and Voronoi Diagrams

   Proceedings of the 14th Algorithms and Data Structures Symposium (WADS), Victoria, Canada, 2015.

   [arXiv] [pdf] [slides]

   Abstract

   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 into cells such that each cell has the same nearest neighbors in S. Classically, both structures can be computed in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s in {1, . . . , n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Theta(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing a triangulation of S in time O(n^2/(s log(s)) + n log(s)) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n^2/s) log(s) + n log(s) log^∗(s)).
5. June 2015
   Haim Kaplan,
   Wolfgang Mulzer,
   Liam Roditty, and
   Paul Seiferth

   Reachability Oracles and Spanners for Directed Transmission Graphs

   Proceedings of the 31st International Symposium on Computational Geometry (SoCG), Eindhoven, Netherlands, 2015.

   [slides]

   Abstract

   Let P be a set of n points in d dimensions, each with an associated radius r_p > 0. The transmission graph G for P has vertex set P and an edge from p to q if and only if q lies in the ball with radius r_p around p. A reachability oracle for G is a data structure that answers reachability queries: given two vertices, is there a directed path between them? The quality of the oracle is measured by the used space S(n),the query time Q(n), and the preproccesing time.

   For d=1, we show how to compute an oracle with Q(n) = O(1) and S(n) = O(n) in time O(n log n). For d=2, we present three different data structures whose quality depends on Psi, the ratio of the largest and smallest radius of two points in P: (i) if Psi < sqrt(3), we achieve Q(n) = O(1) with S(n) = O(n log n); (ii) if Psi is constant, we get Q(n) = O(Psi^3 sqrt(n)) and S(n) = O(Psi^3 n^(3/2)); and (iii) if Psi is polynomially bounded in n, we use probabilistic methods to obtain an oracle with S(n) = O(n^(5/3)log n) and Q(n) = O(n^(2/3)log n) that answers queries correctly with high probability. The construction time is O(n^(5/3)log^2 n).

   To achieve a fast preproccesing time, we show how to compute a t-spanner H for G in time O(n (log n + log Psi)). More precisely, H is a sparse subgraph of G such that for any two vertices p,q connected by a path of length l in G, there is a p-q-path of length at most tl in H. Furthermore, we extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a bonus, it turns out that the properties of our spanner also allow us to compute a BFS tree for G and any given start vertex s in the same time.

6. June 2015
   Wolfgang Mulzer,
   Huy L. Nguyen,
   Paul Seiferth, and
   Yannik Stein

   Approximate k-flat Nearest Neighbor Search

   Proceedings of the 47th Annual Symposium on the Theory of Computing (STOC), Portland, USA, 2015.

   [arXiv] [pdf] [slides]

   Abstract

   Let k be a nonnegative integer. In the approximate k-flat nearest neighbor (k-ANN) problem, we are given a set P of n points in d-dimensional space and a fixed approximation factor c>1. Our goal is to preprocess P so that we can efficiently answer approximate k-flat nearest neighbor queries: given a k-flat F, find a point in P whose distance to F is within a factor c of the distance between F and the closest point in P. The case k=0 corresponds to the well-studied approximate nearest neighbor problem, for which a plethora of results are known, both in low and high dimensions. The case k=1 is called approximate line nearest neighbor. In this case, we are aware of only one provably efficient data structure, due to Andoni, Indyk, Krauthgamer, and Nguyen. For k >= 2, we know of no previous results.

   We present the first efficient data structure that can handle approximate nearest neighbor queries for arbitrary k. We use a data structure for 0-ANN-queries as a black box, and the performance depends on the parameters of the 0-ANN solution: suppose we have an 0-ANN structure with query time O(n^rho) and space requirement O(n^(1+sigma)), for rho,sigma > 0. Then we can answer k-ANN queries in time O(n^(k/(k+1−rho)+t)) and space O(n^(1+sigma k/(k+1−rho))+n log^(O(1/t))n). Here, t>0 is an arbitrary constant and the O-notation hides exponential factors in k, 1/t, and c and polynomials in d. Our new data structures also give an improvement in the space requirement over the previous result for 1-ANN: we can achieve near-linear space and sublinear query time, a further step towards practical applications where space constitutes the bottleneck.

Weakly-Refereed Conferences and Workshops:

1. March 2016
   Haim Kaplan,
   Wolfgang Mulzer,
   Liam Roditty, and
   Paul Seiferth

   Dynamic Connectivity for Unit Disk Graphs

   Proceedings of the 32nd European Workshop on Computational Geometry (EWCG), Lugano, Swiss, 2016.

   [pdf] [slides]

   Abstract

   Let S be a set of point sites in the plane. The unit disk graph UD(S) of S has vertex set S and an edge between two sites s,t if and only if |st| <= 1.

   We present a data structure that maintains the connected components of UD(S) when S changes dynamically. It takes O(log^2 n) time to insert or delete a site in S and O(log n/log log n) time to determine if two sites are in the same connected component. Here, n is the maximum size of S at any time. A simple variant improves the update time to O(log n log log n) at the cost of a slightly increased query time of O(log n).

2. March 2015
   Matias Korman,
   Wolfgang Mulzer,
   André van Renssen,
   Marcel Roeloffzen,
   Paul Seiferth, and
   Yannik Stein

   Time-Space Trade-offs for Voronoi Diagrams

   Proceedings of the 31st European Workshop on Computational Geometry (EWCG), to be appear, Ljubljana, Slovenia, 2015.

   [pdf] [slides]

   Abstract

   Let S be a planar n-point set. Classically, one can find the Voronoi diagram VD(S) for S in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: for s in {1, ..., n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of O(log n) bits for reading and writing intermediate data. We describe a randomized s-workspace algorithm for finding VD(S) in expected time O((n^2/s) log s + n log s log* s). This almost matches the optimal running times for both constant and linear workspace and provides a continuous trade-off between them.
3. March 2015
   Haim Kaplan,
   Wolfgang Mulzer,
   Liam Roditty, and
   Paul Seiferth

   Efficient Spanner Construction for Directed Transmission Graphs

   Proceedings of the 31st European Workshop on Computational Geometry (EWCG), to be appear, Ljubljana, Slovenia, 2015.

   [pdf] [slides]

   Abstract

   Let P be a set of n points in the plane, each with an associated radius r(p) > 0. The transmission graph G for P has vertex set P and a directed edge from p to q if and only if q lies in the ball with radius r(p) around p.

   Let t > 1. A t-spanner H for G is a sparse subgraph such that for any two vertices p and q connected by a path of length l in G, there is a path of length at most tl from p to q in H. Given G implicitly as points with radii, we show how to compute a t-spanner for G in time O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius in P.

4. March 2014
   Haim Kaplan,
   Wolfgang Mulzer,
   Liam Roditty, and
   Paul Seiferth

   Reachability Oracles for Disk Transmission Graphs

   Proceedings of the 30th European Workshop on Computational Geometry (EWCG), Ein-Gedi, Israel, 2014.

   [pdf] [slides]

   Abstract

   Let P be a set of n points in R^d, each with an associated radius r(p) > 0. This induces a directed graph on P with an edge from p to q if and only if q lies in the ball with radius r(p) around p.

   We show that for d=1 there is a data structure that answers reachability queries (given two vertices, is there a directed path between them?) in time O(1) using O(n) space and O(n log n) preprocessing time. With different techniques we can get a similar result for d=2 as long as the radii are between 1 and sqrt(3).

5. March 2013
   Wolfgang Mulzer and
   Paul Seiferth

   Computational Aspects of Triangulations with Bounded Dilation

   Proceedings of the 29th European Workshop on Computational Geometry (EWCG), Brunswick, Germany, 2013.

   [pdf]

   Abstract

   Let T be a triangulation on a planar point set S. If T has bounded dilation, then the shortest path distance between any two vertices approximates their Euclidean distance. We examine if such triangulations can be used to design efficient algorithms for various geometric problems.

   First, we show that given a triangulation with bounded dilation, one can find the closest pair of points in S in linear time on a pointer machine.

   Afterwards, we consider an algorithm by Krznaric and Levcopoulos to compute a hierarchical clustering for S in linear time, once the EMST of S is known. We study how their result can be generalized to MSTs of triangulations with bounded dilation. It turns out that their algorithm remains (almost) correct for any such MST. In general, however, the resulting running time might be superlinear. We identify a sufficient condition for a linear time bound and construct a triangulation without this condition as counterexample.

   It remains open to identify interesting classes of bounded-dilation triangulations with this property.

Technical Reports and Others:

1. November 2012
   Paul Seiferth

   Computational Aspects of Triangulations with Constant Dilation

   Master's Thesis, Freie Universität Berlin

   [pdf]

   Abstract

   Let G be a plane geometric graph. For two distinct vertices u, v of G we can consider the ratio between the length dG (u, v) of the shortest path and the Euclidean distance |u, v| between u and v. The dilation of G is the maximum over all these ratios, i.e. max u,v∈V (G) = d_G(u,v) /|u,v|.

   The aim of this Master Thesis is to examine the geometric properties of triangulations that have bounded dilation and to utilize them in an algorithmic way. Krznaric and Levcopoulos showed that given the Delaunay triangulation for a planar point set S we can compute a hierarchical clustering for S in linear time. We present a similar algorithm that does not insist on the Delaunay triangulation but uses triangulations that have constant dilation. Unfortunately, when analyzing the running time it turned out that the running time of the algorithm is not linear. We identified two properties that are necessary to achieve linear running time. It is left as an open question what kind of triangulations, except for the Delaunay triangulation, fulfill these properties. Furthermore, we state additional properties of triangulations with constant dilation that were encountered during the analysis of the algorithm.