International Journal of Foundations of Computer Science

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, small memory occupation and the possibility of fully dynamic insertions and deletions. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the level below. Point location is done by walking in a triangulation to determine the nearest neighbor of the query at that level, then the walk restarts from the neighbor at the level below. Using a small subset (3%) to sample a level allows a small memory occupation; the walk and the use of the nearest neighbor to change levels quickly locate the query.

Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.

Space-time discontinuous Galerkin (DG) methods provide a solution for a wide variety of numerical problems such as inviscid Burgers equation and elastodynamic analysis. Recent research shows that it is possible to solve a DG system using an element-by-element procedure if the space-time mesh satisfies a cone constraint. This constraint requires that the dihedral angle of each interior mesh face with respect to the space domain is less than or equal to a specified angle function α(). Whenever there is a face that violates the cone constraint, the elements at the face must be coupled in the solution. In this paper we consider the problem of generating a simplicial space-time mesh where the size of each group of elements that need to be coupled is bounded by a constant number k. We present an algorithm for generating such meshes which is valid for any nD×TIME domain (n is a natural number). The k in the algorithm is based on a node degree in an n-dimensional space domain mesh.

We propose sink insertion as a new technique to improve the mesh quality of Delaunay triangulations. We compare it with the conventional circumcenter insertion technique under three scheduling regimes: incremental, in blocks, and in parallel. Justification for sink insertion is given in terms of mesh quality, numerical robustness, running time, and ease of parallelization.

We introduce a new type of subdivision-based multiresolution representation for triangle meshes, kite trees, which has the flexibility to represent arbitrary triangle meshes losslessly. We also develop an algorithm for extracting a balanced kite tree representation of an arbitrary input mesh that preserves mesh topology and regularities in the subdivision structure. Our scheme allows us to combine surface information automatically extracted from input data with algorithmically-generated information in a single multiresolution representation and to represent the results of adaptive refinement of regular subdivision surfaces.

We propose a new scheme for modeling a smooth interpolatory surface, from a surface discretization consisting of triangles, quadrilaterals and pentagons, by algebraic surface patches which are subsets of real zero contours of trivariate rational functions defined on a collection of tetrahedra and pyramids. The rational form of the modeling function provides enough degrees of freedom so that the number of the surface patches is significantly reduced, and the surface has quadratic recover property.

A common operation in fabricating many products is bending a thin, flat sheet of material over a three-dimensional boundary curve that outlines the desired shape. Typically the shape of the closed boundary curve is given, and the geometric problem of interest is to compute the developable surface that forms when the material is bent to conform to this curve. A classical method of solving this problem on the drawing board is by triangulation development: approximating the boundary curve by line segments and the surface by triangles whose vertices are the boundary points. Choosing the proper boundary triangulation was the job of the draftsman. Automating this process on a computer requires identifying triangulations approximating developable surfaces. Moreover, since there are usually two or more developable surfaces that interpolate a given space curve, there must be a means of selecting the most appropriate solution for the application at hand. This paper describes a computer-based method that generates a boundary triangulation by geometrically simulating the bending of the sheet as it would occur during closing of the blankholder in a sheet-metal forming problem.

Let V be a finite point set in 3-space, and let be the set of triangulated polyhedral surfaces homeomorphic to a sphere and with vertex set V. Let abc and cbd be two adjacent triangles belonging to a surface ; the flip of the edge bc would replace these two triangles by the triangles abd and adc. The flip operation is only considered when it does not produce a self-intersecting surface. In this paper we show that given two surfaces S₁, , it is possible that there is no sequence of flips transforming S₁ into S₂, even in the case that V consists of points in convex position.