Sparse geometric graphs with small dilation

Given a set S of n points in , and an integer k such that 0k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.     

Mode excitation in circularly symmetric graded-index optical fibers by focused gaussian beams

Field distributions and propagation constants of modes in weakly guiding circularly symmetric optical waveguides having arbitrary radial refractive index distribution are determinable from a variational analysis, which uses the solution of the scalar wave equation for the infinitely extended parabolic refractive index profile as a reference (Laguerre-Gaussian functions). The power coupling coefficients of the power, which is transferred from a focused Gaussian beam to an LP_vp-mode, depend on frequency and on four normalized launching parameters. Once the field-describing matrix equation has been solved numerically, closed-form expressions are obtained. The condition for optimal matching of the fundamental mode is given, and it is found that the maximum power excitation coefficient may be close to 100% even for substantially disturbed profiles.     

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces

Let Σ be a collection of n algebraic surface patches in of constant maximum degree b, such that the boundary of each surface consists of a constant number of algebraic arcs, each of degree at most b as well. We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement is O(n^{2+ɛ}), for any ɛ > 0, where the constant of proportionality depends on ɛ and on the maximum degree of the surfaces and of their boundaries. As an application, we obtain a near-quadratic motion-planning algorithm for general systems with three degrees of freedom. Received May 30, 1996, and in revised form February 18, 1997.     

Mode excitation in circularly symmetric graded-index optical fibers by focused gaussian beams

Field distributions and propagation constants of modes in weakly guiding circularly symmetric optical waveguides having arbitrary radial refractive index distribution are determinable from a variational analysis, which uses the solution of the scalar wave equation for the infinitely extended parabolic refractive index profile as a reference (Laguerre-Gaussian functions). The power coupling coefficients of the power, which is transferred from a focused Gaussian beam to an LP_vp-mode, depend on frequency and on four normalized launching parameters. Once the field-describing matrix equation has been solved numerically, closed-form expressions are obtained. The condition for optimal matching of the fundamental mode is given, and it is found that the maximum power excitation coefficient may be close to 100% even for substantially disturbed profiles.     

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle α(x,Q) of a point x ∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q⊂C is the minimum aperture angle of any x∈C∖Q with respect to Q. We show that for any compact convex set C in the plane and any k>2, there is an inscribed convex k-gon Q⊂C with aperture angle approximation error . This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k>2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most  . This research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311-D00763). NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

3D Anisotropic Diffusion on GPUs by Closed-Form Local Tensor Computations

We present an efficient implementation of volumetric anisotropic image diffusion filters on modern programmable graphics processing units (GPUs), where the mathematics behind volumetric diffusion is effectively reduced to the diffusion in 2D images. We hereby avoid the computational bottleneck of a time consuming eigenvalue decomposition in $\mathbb{R}^3$. Instead, we use a projection of the Hessian matrix along the surface normal onto the tangent plane of the local isodensity surface and solve for the remaining two tangent space eigenvectors. We derive closed formulas to achieve this and prevent the GPU code from branching. We show that our most complex volumetric anisotropic diffusion filters gain a speed up of more than 600 compared to a CPU solution.     

Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons

A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon on n vertices can be answered in O(log² n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).     

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.