Approximation of the Normal Vector Field and the Area of a Smooth Surface

This paper deals with the comparison of the normal vector field of a smooth surface S with the normal vector field of another surface differentiable almost everywhere. The main result gives an upper bound on angles between the normals of S and the normals of a triangulation T close to S. This upper bound is expressed in terms of the geometry of T, the curvature of S and the Hausdorff distance between both surfaces. This kind of result is really useful: in particular, results of the approximation of the normal vector field of a smooth surface S can induce results of the approximation of the area; indeed, in a very general case (T is only supposed to be locally the graph of a lipschitz function), if we know the angle between the normals of both surfaces, then we can explicitly express the area of S in terms of geometrical invariants of T, the curvature of S and of the Hausdorff distance between both surfaces. We also apply our results in surface reconstruction: we obtain convergence results when T is the restricted Delaunay triangulation of an -sample of S; using Chews algorithm, we also build sequences of triangulations inscribed in S whose curvature measures tend to the curvatures measures of S.     

Orlov spectra: bounds and gaps

The Orlov spectrum is a new invariant of a triangulated category. It was introduced by D. Orlov, building on work of A. Bondal-M. Van den Bergh and R. Rouquier. The supremum of the Orlov spectrum of a triangulated category is called the ultimate dimension. In this work, we study Orlov spectra of triangulated categories arising in mirror symmetry. We introduce the notion of gaps and outline their geometric significance. We provide the first large class of examples where the ultimate dimension is finite: categories of singularities associated to isolated hypersurface singularities. Similarly, given any nonzero object in the bounded derived category of coherent sheaves on a smooth Calabi-Yau hypersurface, we produce a generator, by closing the object under a certain monodromy action, and uniformly bound this generator’s generation time. In addition, we provide new upper bounds on the generation times of exceptional collections and connect generation time to braid group actions to provide a lower bound on the ultimate dimension of the derived Fukaya category of a symplectic surface of genus greater than one.     

Edge Flips in Surface Meshes

Little theoretical work has been done on edge flips in surface meshes despite their popular usage in graphics and solid modeling to improve mesh equality. We propose the class of \((\varepsilon ,\alpha )\)-meshes of a surface that satisfy several properties: the vertex set is an \(\varepsilon \)-sample of the surface, the triangle angles are no smaller than a constant \(\alpha \), some triangle has a good normal, and the mesh is homeomorphic to the surface. We believe that many surface meshes encountered in practice are \((\varepsilon ,\alpha )\)-meshes or close to being one. We prove that flipping the appropriate edges can smooth a dense \((\varepsilon ,\alpha )\)-mesh by making the triangle normals better approximations of the surface normals and the dihedral angles closer to \(\pi \). Moreover, the edge flips can be performed in time linear in the number of vertices. This helps to explain the effectiveness of edge flips as observed in practice and in our experiments. A corollary of our techniques is that, in \(\mathbb {R}^2\), every triangulation with a constant lower bound on the angles can be flipped in linear time to the Delaunay triangulation.     

The focal geometry of circular and conical meshes

Circular meshes are quadrilateral meshes all of whose faces possess a circumcircle, whereas conical meshes are planar quadrilateral meshes where the faces which meet in a vertex are tangent to a right circular cone. Both are amenable to geometric modeling – recently surface approximation and subdivision-like refinement processes have been studied. In this paper we extend the original defining property of conical meshes, namely the existence of face/face offset meshes at constant distance, to circular meshes. We study the close relation between circular and conical meshes, their vertex/vertex and face/face offsets, as well as their discrete normals and focal meshes. In particular we show how to construct a two-parameter family of circular (resp., conical) meshes from a given conical (resp., circular) mesh. We further discuss meshes which have both properties and their relation to discrete surfaces of negative Gaussian curvature. The offset properties of special quadrilateral meshes and the three-dimensional support structures derived from them are highly relevant for computational architectural design of freeform structures. Another aspect important for design is that both circular and conical meshes provide a discretization of the principal curvature lines of a smooth surface, so the mesh polylines represent principal features of the surface described by the mesh.      

Smooth surface reconstruction via natural neighbour interpolation of distance functions

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and accommodates non-uniform samples. The reconstructed surface interpolates the data points and is implicitly represented as the zero set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound, which makes the method especially relevant for small point sets. Experimental results are presented for surfaces in .     

Conformal cochains

In this paper we define holomorphic cochains and an associated period matrix for triangulated closed topological surfaces. We use the combinatorial Hodge star operator introduced in the author's paper of 2007, which depends on the choice of an inner product on the simplicial 1-cochains.

We prove that for a triangulated Riemannian 2-manifold (or a Riemann surface), and a particularly nice choice of inner product, the combinatorial period matrix converges to the (conformal) Riemann period matrix as the mesh of the triangulation tends to zero.

     

Anisotropic a posteriori error estimation for the mixed discontinuous Galerkin approximation of the Stokes problem

This article presents a posteriori error estimates for the mixed discontinuous Galerkin approximation of the stationary Stokes problem. We consider anisotropic finite element discretizations, i.e., elements with very large aspect ratio. Our analysis covers two‐ and three‐dimensional domains. Lower and upper error bounds are proved with minimal assumptions on the meshes. The lower error bound is uniform with respect to the mesh anisotropy. The upper error bound depends on a proper alignment of the anisotropy of the mesh, which is a common feature of anisotropic error estimation. In the special case of isotropic meshes, the results simplify, and upper and lower error bounds hold unconditionally. The numerical experiments confirm the theoretical predictions and show the usefulness of the anisotropic error estimator. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Coverage problems and visibility regions on topographic surfaces

The viewshed of a point on an irregular topographic surface is defined as the area visible from the point. The area visible from a set of points is the union of their viewsheds. We consider the problems of locating the minimum number of viewpoints to see the entire surface, and of locating a fixed number of viewpoints to maximize the area visible, and possible extensions. We discuss alternative methods of representing the surface in digital form, and adopt a TIN or triangulated irregular network as the most suitable data structure. The space is tesselated into a network of irregular triangles whose vertices have known elevations and whose edges join vertices which are Thiessen neighbours, and the surface is represented in each one by a plane. Visibility is approximated as a property of each triangle: a triangle is defined as visible from a point if all of its edges are fully visible. We present algorithms for determination of visibility, and thus reduce the problems to variants of the location set covering and maximal set covering problems. We examine the performance of a variety of heuristics.     

Unfolding of Surfaces

This paper deals with the approximation of the unfolding of a smooth globally developable surface (i.e. "isometric" to a domain of ) with a triangulation. We prove the following result: let T_n be a sequence of globally developable triangulations which tends to a globally developable smooth surface S in the Hausdorff sense. If the normals of T_n tend to the normals of S, then the shape of the unfolding of T_n tends to the shape of the unfolding of S. We also provide several examples: first, we show globally developable triangulations whose vertices are close to globally developable smooth surfaces; we also build sequences of globally developable triangulations inscribed on a sphere, with a number of vertices and edges tending to infinity. Finally, we also give an example of a triangulation with strictly negative Gauss curvature at any interior point, inscribed in a smooth surface with a strictly positive Gauss curvature. The Gauss curvature of these triangulations becomes positive (at each interior vertex) only by switching some of their edges.     

Geometric angle structures on triangulated surfaces

In this paper we characterize the edge invariant and Delaunay invariant of a spherical angle structure on a triangulated surface. We also characterize the edge invariant of a hyperbolic angle structure on a triangulated surface.

     

Analysis of a bilinear finite element for shallow shells I: Approximation of inextensional deformations

We consider a bilinear reduced-strain finite element formulation for a shallow shell model of Reissner-Naghdi type. The formulation is closely related to the facet models used in engineering practice. We estimate the error of this scheme when approximating an inextensional displacement field. We make the strong assumptions that the domain and the finite element mesh are rectangular and that the boundary conditions are periodic and the mesh uniform in one of the coordinate directions. We prove then that for sufficiently smooth fields, the convergence rate in the energy norm is of optimal order uniformly with respect to the shell thickness. In case of elliptic shell geometry the error bound is furthermore quasioptimal, whereas in parabolic and hyperbolic geometries slightly enhanced smoothness is required, except for the degenerate cases where the characteristic lines are parallel with the mesh lines. The error bound is shown to be sharp.

     

The hp‐version of the BEM with quasi‐uniform meshes for a three‐dimensional crack problem: The case of a smooth crack having smooth boundary curve

The article considers a three‐dimensional crack problem in linear elasticity with Dirichlet boundary conditions. The crack in this model problem is assumed to be a smooth open surface with smooth boundary curve. The hp‐version of the boundary element method with weakly singular operator is applied to approximate the unknown jump of the traction which is not L₂‐regular due to strong edge singularities. Assuming quasi‐uniform meshes and uniform distributions of polynomial degrees, we prove an a priori error estimate in the energy norm. The estimate gives an upper bound for the error in terms of the mesh size h and the polynomial degree p. It is optimal in h for any given data and quasi‐optimal in p for sufficiently smooth data. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

On Plateau’s problem for soap films with a bound on energy

We prove existence and almost everywhere regularity of an area minimizing soap film with a bound on energy spanning a given Jordan curve in Euclidean space R ³.The energy of a film is defined to be the sum of its surface area and the length of its singular branched set. The class of surfaces over which area is minimized includes images of disks, integral currents, nonorientable surfaces and soap films as observed by Plateau with a bound on energy. Our area minimizing solution is shown to be a smooth surface away from its branched set which is a union of Lipschitz Jordan curves of finite total length.     

Elastic-plastic halfspace simulation

Due to the roughness of technical surfaces only the surface peaks are in contact for moderate contact pressures. Thus, the real contact area is smaller than the apparent contact area. Contact forces can only occur in the real contact area. Consequently it is necessary to determine the deformation of surface asperities in order to analyse the tribological properties of surfaces. The real contact area is usually small in initial contact. This leads to large contact pressures which in turn lead to the plastic deformation of surface roughness peaks. Therefore an elastic-plastic model is necessary. The halfspace model seems to be beneficial because there is only a system of equations on a surface mesh to be solved and not on a volume mesh like in the Finite-Element-Method. This leads to a much smaller system of equations which should allow reasonable calculation times even for large contact surfaces. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Improving an Upper Bound on the Stability Number of a Graph

In previous works an upper bound on the stability number of a graph based on quadratic programming was introduced and several of its properties were given. The graphs for which this bound is attained has been known as graphs with convex-QP stability number. This paper proposes a new upper bound on the stability number whose determination is also done by quadratic programming. It is proved that the new bound improves the above mentioned bound and several computational tests asserting its interest for large graphs are presented. In addition a necessary and sufficient condition for a graph to attain the new bound is proved. As a consequence a graph with convex-QP stability number also attains the new bound. On the other hand it is shown the existence of graphs attaining the new bound that do not belong to the class of graphs with convex-QP stability number. This allows to assert that the class of graphs with convex-QP stability number is strictly included in the class of graphs that attain the introduced bound. Some conclusions and lines for future work finalize the paper.     

基于中心路径大邻域上的一类非单调线性互补问题的高阶可行内点算法

In this paper a high-order feasible interior point algorithm for a class of nonmonotonic (P-matrix) linear complementary problem based on large neighborhoods of central path is presented and its iteration complexity is discussed.These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms bound depends on the size of the neighborhood. It is well known that the complexity of large-step algorithms is greater than that of short- step ones. By using high-order power series (hence the name high-order algorithms), the iteration complexity can be reduced. We show that the upper bound of complexity for our high-order algorithms is equal to that for short-step algorithms.     

Coloring vertices and faces of maps on surfaces

The vertex-face chromatic number of a map on a surface is the minimum integer m such that the vertices and faces of the map can be colored by m colors in such a way that adjacent or incident elements receive distinct colors. The vertex-face chromatic number of a surface is the maximal vertex-chromatic number for all maps on the surface. We give an upper bound on the vertex-face chromatic number of the surfaces of Euler genus ≥2. The upper bound is less (by 1) than Ringel’s upper bound on the 1-chromatic number of a surface for about 5/12 of all surfaces. We show that there are good grounds to suppose that the upper bound on the vertex-face chromatic number is tight.     

Inverse inequality estimates with symbolic computation

In the convergence analysis of numerical methods for solving partial differential equations (such as finite element methods) one arrives at certain generalized eigenvalue problems, whose maximal eigenvalues need to be estimated as accurately as possible. We apply symbolic computation methods to the situation of square elements and are able to improve the previously known upper bound, given in “p- and hp-finite element methods” (Schwab, 1998), by a factor of 8. More precisely, we try to evaluate the corresponding determinant using the holonomic ansatz, which is a powerful tool for dealing with determinants, proposed by Zeilberger in 2007. However, it turns out that this method does not succeed on the problem at hand. As a solution we present a variation of the original holonomic ansatz that is applicable to a larger class of determinants, including the one we are dealing with here. We obtain an explicit closed form for the determinant, whose special form enables us to derive new and tight upper resp. lower bounds on the maximal eigenvalue, as well as its asymptotic behaviour.     

Fundamental groups of open K3 surfaces, Enriques surfaces and Fano 3-folds

We investigate when the fundamental group of the smooth part of a K3 surface or Enriques surface with Du Val singularities, is finite. As a corollary we give an effective upper bound for the order of the fundamental group of the smooth part of a certain Fano 3-fold. This result supports Conjecture A below, while Conjecture A (or alternatively the rational-connectedness conjecture in Kollar et al. (J. Algebra Geom. 1 (1992) 429) which is still open when the dimension is at least 4) would imply that every log terminal Fano variety has a finite fundamental group.     

Concerning the shape of a geometric lattice

A well-known conjecture states that the Whitney numbers of the second kind of a geometric lattice (simple matroid) are logarithmically concave. We show this conjecture to be equivalent to proving an upper bound on the number of new copoints in the free erection of the associated simple matroid M. A bound on the number of these new copoints is given in terms of the copoints and colines of M. Also, the points-lines-planes conjecture is shown to be equivalent to a problem concerning the number of subgraphs of a certain bipartite graph whose vertices are the points and lines of a geometric lattice.