27 research outputs found
Summary Report Of Working Group 8: Laser Technology For Laser-Plasma Accelerators
No full textLaser Technology has long been the limiting and the enabling step for laser plasma accelerators. The work presented here addressed the current and near future laser technology relevant to particle acceleration as well as laser technology challenges for future accelerator facilities. Many laser facilities are operating or will be operating shortly at high intensity, high peak power, and with good beam parameters.Physic
On the Upward Planarity of Mixed Plane Graphs
No full textA mixed plane graph is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An orientation of a mixed plane graph G is an assignment of directions to the undirected edges of G resulting in a directed plane graph TeX . In this paper, we study the computational complexity of testing whether a given mixed plane graph G is upward planar, i.e., whether it admits an orientation resulting in a directed plane graph G such that G admits a planar drawing in which each edge is represented by a curve monotonically increasing in the y-direction according to its orientation.
Our contribution is threefold. First, we show that the upward planarity testing problem is solvable in cubic time for mixed outerplane graphs. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of mixed plane triangulations. Third, we exhibit linear-time testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3-trees and mixed plane triangulations in which the undirected edges induce a forest
Constant-Factor Approximation for TSP with Disks
No full textWe revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of n disks in the plane, a TSP tour whose length is at most O(1) times the optimal with high probability can be computed in time that is polynomial in n. Our result is the first constant-ratio approximation for a class of planar convex bodies of arbitrary size and arbitrary intersections. In order to achieve a O(1)-approximation, we reduce the traveling salesman problem with disks, up to constant factors, to a minimum weight hitting set problem in a geometric hyper-graph. The connection between TSPN and hitting sets in geometric hypergraphs, established here, is likely to have future applications
Graph drawing and network visualization: 27th international symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, proceedings
No full textPacking anchored rectangles
No full textLet S be a set of n points in the unit square [0, 1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.
Covering Paths for Planar Point Sets
No full textGiven a set of points, a covering path is a directed polygonal path that visits all the points. We show that for any n points in the plane, there exists a (possibly self-crossing) covering path consisting of straight line segments. If no three points are collinear, any covering path (self-crossing or non-crossing) needs at least segments. If the path is required to be non-crossing, straight line segments obviously suffice and we exhibit n-element point sets which require at least segments in any such path. Further, we show that computing a non-crossing covering path for n points in the plane requires Ω(n logn) time in the worst case
