An upper bound for conforming Delaunay triangulations

A plane geometric graphC in ℝ² conforms to another such graphG if each edge ofG is the union of some edges ofC. It is proved that, for everyG withn vertices andm edges, there is a completion of a Delaunay triangulation ofO(m ² n) points that conforms toG. The algorithm that constructs the points is also described. Research of the first author is supported by the National Science Foundation under Grant CCR-8921421 and under the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Work of the second author was conducted while he was on study leave at the University of Illinois.     

Edge insertion for optimal triangulations

Edge insertion iteratively improves a triangulation of a finite point set in ℜ² by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface. The research of the second author was supported by the National Science Foundation under Grant No. CCR-8921421 and under the Alan T. Waterman award, Grant No. CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Part of the work was done while the second, third, and fourth authors visited the Xerox Palo Alto Research Center, and while the fifth author was on study leave at the University of Illinois.     

An optimal perturbation bound

Cai and Zhang establish separate perturbation bounds for distances with spectral and Frobenius norms (Cai T, Zhang A. Rate‐optimal perturbation bounds for singular subspaces with applications to high‐dimensional statistics. The Annals of Statistics. 2018; Vol. 46, No. 1: 60?89). We extend their theorem to each unitarily invariant norm. It turns out that our estimation is optimal as well.     

An optimal lower bound for the Frobenius problem

Given N?2 positive integers a₁,a₂,…,aN with GCD(a₁,…,aN)=1, let fN denote the largest natural number which is not a positive integer combination of a₁,…,aN. This paper gives an optimal lower bound for fN in terms of the absolute inhomogeneous minimum of the standard (N−1)-simplex.     

Algorithms for optimal area triangulations of a convex polygon

Given a convex polygon with n vertices in the plane, we are interested in triangulations of its interior, i.e., maximal sets of non-intersecting diagonals that subdivide the interior of the polygon into triangles. The MaxMin area triangulation is the triangulation of the polygon that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. We present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in O(n²logn) time and O(n²) space. The algorithms use dynamic programming and a number of geometric properties that are established within the paper.     

An optimal bound for the spectral variation of two matrices

We establish a bound for the spectral variation of two complex n × n matrices A,B in terms of ∥A∥, ∥B∥, and ∥A ? B∥. Here ∥ ∥ denotes the spectral norm. It is always better than a bound previously given by Bhatia and Friedland, and it is optimal. We describe the set of pairs A,B for which the bound is attained.     

An optimal piecewise cubic nonconforming finite element scheme for the planar biharmonic equation on general triangulations

This paper presents a nonconforming finite element scheme for the planar biharmonic equation,which applies piecewise cubic polynomials(P_3) and possesses O(h~2) convergence rate for smooth solutions in the energy norm on general shape-regular triangulations. Both Dirichlet and Navier type boundary value problems are studied. The basis for the scheme is a piecewise cubic polynomial space, which can approximate the H4 functions with O(h2) accuracy in the broken H~2 norm. Besides, a discrete strengthened Miranda-Talenti estimate(▽_h~2·,▽_h~2·) =(?h·, ?h·), which is usually not true for nonconforming finite element spaces, is proved.The finite element space does not correspond to a finite element defined with Ciarlet's triple; however, it admits a set of locally supported basis functions and can thus be implemented by the usual routine. The notion of the finite element Stokes complex plays an important role in the analysis as well as the construction of the basis functions.     

An optimal bound for inverses of triangular matrices with monotone entries

This article provides a new bound for 1-norms of inverses of positive triangular matrices with monotonic column entries. The main theorem refines a recent inequality established in Vecchio and Mallik [Bounds on the inverses of non-negative lower triangular Toeplitz matrices with monotonicity properties, Linear Multilinear Alg., 55 (2007), pp. 365–379]. The results are shown to be in a sense best possible under the given constraints.     

An efficient algorithm for enumeration of triangulations

We consider the problem of enumerating triangulations of n points in the plane in general position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in O(loglogn) time per triangulation. It improves the previous bound by almost linear factor.     

An improved bound on the optimal paper Moebius band

Geometriae Dedicata - We show that a smooth embedded paper Moebius band must have aspect ratio at least $$begin{aligned}lambda _1= frac{2 sqrt{4-2 sqrt{3}}+4}{root 4 of {3} sqrt{2}+2...     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

An optimal lower bound for the discrepancy of c-uniformly distributed functions modulo

It is proved that a lower bound for the discrepancy D_T(ω) of a continuous function ω(t) modulo 1 is given by ϕ(s(T)) infinitely often, where ϕ(x) is integrable on [0, ∞). This bound is best possible in the one dimensional case. Furthermore a generalization to compact, metric spaces is given.     

Risk-averse stochastic optimal control: An efficiently computable statistical upper bound

In this paper, we discuss an application of the Stochastic Dual Dynamic Programming (SDDP) type algorithm to nested risk-averse formulations of Stochastic Optimal Control (SOC) problems. We propose a construction of a statistical upper bound for the optimal value of risk-averse SOC problems. This outlines an approach to a solution of a long standing problem in that area of research. The bound holds for a large class of convex and monotone conditional risk mappings. Finally, we show the validity of the statistical upper bound to solve a real-life stochastic hydro-thermal planning problem.     

An efficient direct method for fully conforming spectral collocation schemes

An efficient direct method is presented for the solution of the linear systems arising in the solution of second and fourth order problems by certain multidomain spectral collocation schemes. In it, the block structure of the global matrix is exploited. The performance of the method is examined for problems in two and three dimensions on an RS6000 workstation and a Cray J-916 supercomputer.     

Recursive constructions for triangulations

Three recursive constructions are presented; two deal with embeddings of complete graphs and one with embeddings of complete tripartite graphs. All three facilitate the construction of 2) non‐isomorphic face 2‐colourable triangulations of K_n and K_n,n,n in orientable and non‐orientable surfaces for values of n lying in certain residue classes and for appropriate constants a. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 87–107, 2002     

A lower bound for the optimal crossing-free Hamiltonian cycle problem

Consider a drawing in the plane ofK _n , the complete graph onn vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing ofK _n . If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let (n) represent the maximum number of cfhc's of any drawing ofK _n , and (n) the maximum number of cfhc's of any rectilinear drawing ofK _n . The problem of determining (n) and (n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for (n) and (n). In particular, it is shown that (n) is at leastk × 3.2684 ⁿ . We conjecture that both (n) and (n) are at mostc × 4.5 ⁿ .This research, part of which was conducted at Queen's University, was supported by an N.S.E.R.C. postgraduate scholarship.     

An unavoidable set of configurations in planar triangulations

Let T be a normal triangulation (considered in the context of the four-color problem). Assume that no two vertices of degree 5 are adjacent. Then T contains at least 1 of the 47 configurations in Table I all of which are likely to be 4-color reducible.     

An inequality for polyhedra and ideal triangulations of cusped hyperbolic 3-manifolds

It is not known whether every noncompact hyperbolic 3-manifold of finite volume admits a decomposition into ideal tetrahedra. We give a partial solution to this problem: Let be a hyperbolic 3-manifold obtained by identifying the faces of convex ideal polyhedra . If the faces of are glued to , then can be decomposed into ideal tetrahedra by subdividing the 's.