A metric tree embedding of expected stretch α ≥ 1 maps a weighted n -node graph G = ( V , E , ω) to a weighted tree T = ( V T , E T , ω T ) with V ⊑ V T such that, for all v , w ∈ V , dist( v , w , G ) ≤ dist( v , w , T ), and E[dist( v , w , T )] ≤ α dist( v , w , G ). Such embeddings are highly useful for designing fast approximation algorithms as many hard problems are easy to solve on tree instances. However, to date, the best parallel polylog n )-depth algorithm that achieves an asymptotically optimal expected stretch of α ∈ O(log n ) requires Ω ( n 2 ) work and a metric as input. In this article, we show how to achieve the same guarantees using polylog n depth and Õ( m 1+ε ) work, where m = | E | and ε > 0 is an arbitrarily small constant. Moreover, one may further reduce the work to Õ( m + n 1+ε ) at the expense of increasing the expected stretch to O(ε −1 log n ). Our main tool in deriving these parallel algorithms is an algebraic characterization of a generalization of the classic Moore-Bellman-Ford algorithm. We consider this framework, which subsumes a variety of previous “Moore-Bellman-Ford-like” algorithms, to be of independent interest and discuss it in depth. In our tree embedding algorithm, we leverage it to provide efficient query access to an approximate metric that allows sampling the tree using polylog n depth and Õ( m ) work. We illustrate the generality and versatility of our techniques by various examples and a number of additional results. Specifically, we (1) improve the state of the art for determining metric tree embeddings in the Congest model, (2) determine a (1 + εˆ)-approximate metric regarding the distances in a graph G in polylogarithmic depth and Õ( n ( m + n 1 + ε )) work, and (3) improve upon the state of the art regarding the k -median and the buy-at-bulk network design problems.

In digital circuits, metastability can cause deteriorated signals that neither are logical 0 nor logical 1, breaking the abstraction of Boolean logic. Synchronizers, the only traditional countermeasure, exponentially decrease the odds of maintained metastability overtime. We propose a fundamentally different approach: It is possible to deterministically contain metastability by fine-grained logical masking so that it cannot infect the entire circuit. At the heart of our approach lies a time- and value-discrete model for metastability in synchronous clocked digital circuits, in which metastability is propagated in a worst-case fashion. The proposed model permits positive results and passes the test of reproducing Marino's impossibility results. We fully classify which functions can be computed by circuits with standard registers. Regarding masking registers, we show that more functions become computable with each clock cycle, and that masking registers permit exponentially smaller circuits for some tasks. Demonstrating the applicability of our approach, we present the first fault-tolerant distributed clock synchronization algorithm that deterministically guarantees correct behavior in the presence of metastability. As a consequence, clock domains can be synchronized without using synchronizers, enabling metastability-free communication between them.

The art gallery problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a given polygon. The AGP is well-known to be NP-hard even in restricted cases. In this paper, we consider the AGP with fading (AGPF): A polygonal region is to be illuminated with light sources such that every point is illuminated with at least a global threshold, light intensity decreases over distance, and we seek to minimize the total energy consumption. Choosing fading exponents of zero, one, and two are equivalent to the AGP, laser scanner applications, and natural light, respectively. We present complexity results as well as a negative solvability result. Still, we propose two practical algorithms for AGPF with fixed light positions (e.g. vertex guards) independent of the fading exponent, which we demonstrate to work well in practice. One is based on a discrete approximation, the other on non-linear programming by means of simplex-partitioning strategies. The former approach yields a fully polynomial-time approximation scheme for the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation.

A metric tree embedding of expected stretch α maps a weighted n-node graph G = (V, E, w) to a weighted tree T = (VT, ET, wT) with V ⊆ VT, and dist(v, w, G) ≤ dist(v, w, T) and E[dist(v, w, T)] ≤ α dist(v, w, G) for all v, w ∈ V. Such embeddings are highly useful for designing fast approximation algorithms, as many hard problems are easy to solve on tree instances. However, to date the best parallel polylog n depth algorithm that achieves an asymptotically optimal expected stretch of α ∈ Ω(log n) uses Ω(n2) work and requires a metric as input.

Automated valet parking not only improves driving comfort, but can have a considerable impact on the urban landscape by reducing the required parking space. We present the first study of parking space optimization for automated valet parking with an in-depth theoretical analysis of the parking lot properties under various aspects, inluding the worst-case extraction time, total shunting distance, and the number of shunting operations (each per car). Most importantly, the proposed model bounds all these values. We verify the theoretical properties of our model in four simulated scenarios, one of which is based on real-world data from a downtown parking garage. We show that very good pick-up times of about 1 min are possible with very little overhead in terms of shunting distance and time, while providing a significantly improved parking density as compared to conventional parking lots.

In this video, we illustrate how one of the classical areas of computational geometry has gained in practical relevance, which in turn gives rise to new, fascinating geometric problems. In particular, we demonstrate how the robot platform IRMA3D can produce high-resolution, virtual 3D environments, based on a limited number of laser scans. Computing an optimal set of scans amounts to solving an instance of the Art Gallery Problem (AGP): Place a minimum number of stationary guards in a polygonal region P, such that all points in P are guarded.