Topological sweep of the complete graph

We present a novel, simple and easily implementable algorithm to report all intersections in an embedding of a complete graph. For graphs with N vertices and complexity K measured as the number of segments of the embedding, the running time of the algorithm is Θ(K+NM), where M is the maximum number of edges cut by any vertical line. Our algorithm handles degeneracies, such as vertical edges or multiply intersecting edges, without requiring numerical perturbations to achieve general position.The algorithm is based on the sweep line technique, one of the most fundamental techniques in computational geometry, where an imaginary line passes through a given set of geometric objects, usually from left to right. The algorithm sweeps the graph using a topological line, borrowing the concept of horizon trees from the topological sweep method [H. Edelsbrunner, L.J. Guibas, Topologically sweeping an arrangement, J. Comput. Syst. Sci. 38 (1989) 165-194; J. Comput. Syst. Sci. 42 (1991) 249-251 (corrigendum)].The novelty in our approach is to control the topological line through the use of the moving wall that separates at any time the graph into two regions: the region of known structure, in front of the moving wall, and the region that may contain intersections generated by edges-that have not yet been registered in the sweep process-behind the wall.Our method has applications to graph drawing and for depth-based statistical analysis, for computing the simplicial depth median for a set of N data points [G. Aloupis, S. Langerman, M. Soss, G. Toussaint, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comp. Geom. Theory Appl. 26 (1) (2003) 69-79].We present the algorithm, its analysis, experimental results and extension of the method to general graphs.     

Visible-Light Photochemical Reduction of CO2 to CO Coupled to Hydrocarbon Dehydrogenation

Research on the photochemical reduction of CO₂, initiated already 40 years ago, has with few exceptions been performed by using amines as sacrificial reductants. Hydrocarbons are high-volume chemicals whose dehydrogenation is of interest, so the coupling of a CO₂ photoreduction to a hydrocarbon-photodehydrogenation reaction seems a worthwhile concept to explore. A three-component construct was prepared including graphitic carbon nitride (g-CN) as a visible-light photoactive semiconductor, a polyoxometalate (POM) that functions as an electron acceptor to improve hole–electron charge separation, and an electron donor to a rhenium-based CO₂ reduction catalyst. Upon photoactivation of g-CN, a cascade is initiated by dehydrogenation of hydrocarbons coupled to the reduction of the polyoxometalate. Visible-light photoexcitation of the reduced polyoxometalate enables electron transfer to the rhenium-based catalyst active for the selective reduction of CO₂ to CO. The construct was characterized by zeta potential, IR spectroscopy, thermogravimetry, scanning electron microscopy (SEM) and energy dispersive X-ray spectroscopy (EDS). An experimental Z-scheme diagram is presented based on electrochemical measurements and UV/Vis spectroscopy. The conceptual advance should promote study into more active systems.     

Visible‐Light Photochemical Reduction of CO2 to CO Coupled to Hydrocarbon Dehydrogenation

Research on the photochemical reduction of CO₂, initiated already 40 years ago, has with few exceptions been performed by using amines as sacrificial reductants. Hydrocarbons are high‐volume chemicals whose dehydrogenation is of interest, so the coupling of a CO₂ photoreduction to a hydrocarbon‐photodehydrogenation reaction seems a worthwhile concept to explore. A three‐component construct was prepared including graphitic carbon nitride (g‐CN) as a visible‐light photoactive semiconductor, a polyoxometalate (POM) that functions as an electron acceptor to improve hole–electron charge separation, and an electron donor to a rhenium‐based CO₂ reduction catalyst. Upon photoactivation of g‐CN, a cascade is initiated by dehydrogenation of hydrocarbons coupled to the reduction of the polyoxometalate. Visible‐light photoexcitation of the reduced polyoxometalate enables electron transfer to the rhenium‐based catalyst active for the selective reduction of CO₂ to CO. The construct was characterized by zeta potential, IR spectroscopy, thermogravimetry, scanning electron microscopy (SEM) and energy dispersive X‐ray spectroscopy (EDS). An experimental Z‐scheme diagram is presented based on electrochemical measurements and UV/Vis spectroscopy. The conceptual advance should promote study into more active systems.     

Cuttings for Disks and Axis-Aligned Rectangles in Three-Space

We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈?, a $\frac{1}{r}We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈ℕ, a \frac1r\frac{1}{r} -cutting is a covering of the space with simplices such that the interior of each simplex intersects at most n/r objects. For n pairwise disjoint disks in ℝ³ and a parameter r∈ℕ, we construct a \frac1r\frac{1}{r} -cutting of size O(r ²). For n axis-aligned rectangles in ℝ³, we construct a \frac1r\frac{1}{r} -cutting of size O(r ^3/2). As an application related to multi-point location in three-space, we present tight bounds on the cost of spanning trees across barriers. Given n points and a finite set of disjoint disk barriers in ℝ³, the points can be connected with a straight line spanning tree such that every disk is stabbed by at most O(?n)O(\sqrt{n}) edges of the tree. If the barriers are axis-aligned rectangles, then there is a straight line spanning tree such that every rectangle is stabbed by O(n ^1/3) edges. Both bounds are best possible.     

Tight Bounds for Connecting Sites Across Barriers

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines, it is known that there is a spanning tree such that every barrier is crossed by tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost. We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular, we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are the best possible. Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027. E. Rafalin’s research conducted while at Tufts University.