Spanning Trees Crossing Few Barriers

We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of $m$ barriers. We obtain the following results: (i) if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost $O(\min(m^2,m\sqrt{n}))$; (ii) if the barriers are disjoint line segments, then there is always a spanning tree of cost $O(m)$; (iii) ] if the barriers are disjoint convex objects, then there is always a spanning tree of cost $O(n+m)$. All our bounds are worst-case optimal, up to multiplicative constants.     

The Voronoi Diagram of Curved Objects

Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or even a two-dimensional object; there are Voronoi edges between different parts of the same site (so-called self-Voronoi-edges); these self-Voronoi-edges may end at seemingly arbitrary points not on a site, and, in the case of a circular site, even degenerate to a single isolated point. We give a systematic study of these phenomena, characterizing their differential-geometric and topological properties. We show how a given set of curves can be refined such that the resulting curves define a “well-behaved” Voronoi diagram. We also give a randomized incremental algorithm to compute this diagram. The expected running time of this algorithm is O(n log n).     

Area-preserving approximations of polygonal paths

Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let W_A(Q) be the area above P and below Q, and let W_B(Q) be the area above Q and below P. Given P and an integer k, we show how to compute a path Q with at most k edges that minimizes W_A(Q)+W_B(Q). Given P and a cost C, we show how to find a path Q with the smallest possible number of edges such that W_A(Q)+W_B(Q)C. However, given P, an integer k, and a cost C, it is NP-hard to determine if a path Q with at most k edges exists such that max{W_A(Q),W_B(Q)}C. We describe an approximation algorithm for this setting. Finally, it is also NP-hard to decide whether a path Q exists such that |W_A(Q)−W_B(Q)|=0. Nevertheless, in this error measure we provide an algorithm for computing an optimal approximation up to an additive error.     

Experimental observation of an entire family of four-photon entangled states

A single linear-optical setup is used to observe an entire family of four-photon entangled states. This approach breaks with the inflexibility of present linear-optical setups usually designed for the observation of a particular multipartite entangled state only. The family includes several prominent entangled states that are known to be highly relevant for quantum information applications.     

Bell inequalities for graph states

We investigate the nonlocal properties of graph states. To this aim, we derive a family of Bell inequalities which require three measurement settings for each party and are maximally violated by graph states. In turn, for each graph state there is an inequality maximally violated only by that state. We show that for certain types of graph states the violation of these inequalities increases exponentially with the number of qubits. We also discuss connections to other entanglement properties such as the positivity of the partial transpose or the geometric measure of entanglement.     

Finding a Guard that Sees Most and a Shop that Sells Most

We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set in the plane. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time, and the rigid motion doing so in near-cubic time.