Abstract In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or combining of partial solutions and filtering of dominated solutions in the resulting sets. In this article, we consider the task of computing the Pareto sum of two given Pareto sets A, B of size n. The Pareto sum C contains all non-dominated points of the Minkowski sum $$M = \{a+b|a \in A, b\in B\}$$ M = { a + b | a ∈ A , b ∈ B } . Since the Minkowski sum has a size of $$n^2$$ n 2 , but the Pareto sum C can be much smaller, the goal is to compute C without having to compute and store all of M. We present several new algorithms for efficient Pareto sum computation, including an output-sensitive successive algorithm with a running time of $$\mathcal {O}(n \log n + nk)$$ O ( n log n + n k ) and a space consumption of $$\mathcal {O}(n+k)$$ O ( n + k ) for $$k=|C|$$ k = | C | . If the elements of C are streamed, the space consumption reduces to $$\mathcal {O}(n)$$ O ( n ) . For output sizes $$k \ge 2n$$ k ≥ 2 n , we prove a conditional lower bound for Pareto sum computation, which excludes running times in $$\mathcal {O}(n^{2-\delta })$$ O ( n 2 - δ ) for $$\delta > 0$$ δ > 0 unless the (min,+)-convolution hardness conjecture fails. The successive algorithm matches this lower bound for $$k \in \Theta (n)$$ k ∈ Θ ( n ) . However, for $$k \in \Theta (n^2)$$ k ∈ Θ ( n 2 ) , the successive algorithm exhibits a cubic running time. But we also present an algorithm with an output-sensitive space consumption and a running time of $$\mathcal {O}(n^2 \log n)$$ O ( n 2 log n ) , which matches the lower bound up to a logarithmic factor even for large k. Furthermore, we describe suitable engineering techniques to improve the practical running times of our algorithms. Finally, we provide an extensive comparative experimental study on generated and real-world data. As a showcase application, we consider preprocessing-based bi-criteria route planning in road networks. Pareto sum computation is the bottleneck task in the preprocessing phase and in the query phase. We show that using our algorithms with an output-sensitive space consumption allows to tackle larger instances and reduces the preprocessing and query time compared to algorithms that fully store M.

One established metric to classify the significance of a mountain peak is its isolation. It specifies the distance between a peak and the closest point of higher elevation. Peaks with high isolation dominate their surroundings and provide a nice view from the top. With the availability of worldwide Digital Elevation Models (DEMs), the isolation of all mountain peaks can be computed automatically. Previous algorithms run in worst case time that is quadratic in the input size. We present a novel sweep-plane algorithm that runs in time 𝒪(nlog n+pT_NN) where n is the input size, p the number of considered peaks and T_NN the time for a 2D nearest-neighbor query in an appropriate geometric search tree. We refine this to a two-level approach that has high locality and good parallel scalability. Our implementation reduces the time for calculating the isolation of every peak on Earth from hours to minutes while improving precision.

Yao graphs are geometric spanners that connect each point of a given point set to its nearest neighbor in each of $k$ cones drawn around it. Yao graphs were introduced to construct minimum spanning trees in $d$ dimensional spaces. Moreover, they are used for instance in topology control in wireless networks. An optimal \Onlogn time algorithm to construct Yao graphs for given point set has been proposed in the literature but -- to the best of our knowledge -- never been implemented. Instead, algorithms with a quadratic complexity are used in popular packages to construct these graphs. In this paper we present the first implementation of the optimal Yao graph algorithm. We develop and tune the data structures required to achieve the O(n log n) bound and detail algorithmic adaptions necessary to take the original algorithm from theory to practice. We propose a priority queue data structure that separates static and dynamic events and might be of independent interest for other sweepline algorithms. Additionally, we propose a new Yao graph algorithm based on a uniform grid data structure that performs well for medium-sized inputs. We evaluate our implementations on a wide variety synthetic and real-world datasets and show that our implementation outperforms current publicly available implementations by at least an order of magnitude.

Computing the Delaunay triangulation (DT) of a given point set in ℝD is one of the fundamental operations in computational geometry. In this paper we present a novel divide-and-conquer (D&C) algorithm that lends itself equally well to shared and distributed memory parallelism. While previous D&C algorithms generally suffer from a complex – often sequential – merge or divide step, we reduce the merging of two partial triangulations to re-triangulating a small subset of their vertices using the same parallel algorithm and combining the three triangulations via parallel hash table lookups. In experiments we achieve a reasonable speedup on shared memory machines and compare favorably to CGAL's three-dimensional parallel DT implementation on some inputs. In the distributed memory setting we show that our approach scales to 2048 processing elements, which allows us to compute 3-D DTs for inputs with billions of points.