Centroidal Voronoi tessellations （CVTs） have become a useful tool in many applications ranging from geometric modeling, image and data analysis, and numerical partial differential equations, to problems in physics, astrophysics, chemistry, and biology. In this paper, we briefly review the CVT concept and a few of its generalizations and well-known properties. We then present an overview of recent advances in both mathematical and computational studies and in practical applications of CVTs. Whenever possible, we point out some outstanding issues that still need investigating.

We compare various algorithms for constructing a matrix of order $$n$$ whose Pareto spectrum contains a prescribed set $$\Lambda =\{\lambda _1,\ldots , \lambda _p\}$$ of reals. In order to avoid overdetermination one assumes that $$p$$ does not exceed $$n^2.$$ The inverse Pareto eigenvalue problem under consideration is formulated as an underdetermined system of nonlinear equations. We also address the issue of computing Lorentz spectra and solving inverse Lorentz eigenvalue problems.

In this paper, we present an efficient approach for unsupervised segmentation of natural and textural images based on the extraction of image features and a fast active contour segmentation model. We address the problem of textures where neither the gray-level information nor the boundary information is adequate for object extraction. This is often the case of natural images composed of both homogeneous and textured regions. Because these images cannot be in general directly processed by the gray-level information, we propose a new texture descriptor which intrinsically defines the geometry of textures using semi-local image information and tools from differential geometry. Then, we use the popular Kullback-Leibler distance to design an active contour model which distinguishes the background and textures of interest. The existence of a minimizing solution to the proposed segmentation model is proven. Finally, a texture segmentation algorithm based on the Split-Bregrnan method is introduced to extract meaningful objects in a fast way. Promising synthetic and real-world results for gray-scale and color images are presented.

In this paper, a class of new immersed interface finite element methods （IIFEM） is developed to solve elasticity interface problems with homogeneous and non-homogeneous jump conditions in two dimensions. Simple non-body-fitted meshes are used. For homogeneous jump conditions, both non-conforming and conforming basis functions are constructed in such a way that they satisfy the natural jump conditions. For non-homogeneous jump conditions, a pair of functions that satisfy the same non-homogeneous jump conditions are constructed using a level-set representation of the interface. With such a pair of functions, the discontinuities across the interface in the solution and flux are removed; and an equivalent elasticity interface problem with homogeneous jump conditions is formulated. Numerical examples are presented to demonstrate that such methods have second order convergence.

Local mesh refinement is one of the key steps in the implementations of adaptive finite element methods. This paper presents a parallel algorithm for distributed memory parallel computers for adaptive local refinement of tetrahedral meshes using bisection. This algorithm is used in PHG, Parallel Hierarchical Grid Chttp：//lsec. cc. ac. cn/phg/）, a toolbox under active development for parallel adaptive finite element solutions of partial differential equations. The algorithm proposed is characterized by allowing simukaneous refinement of submeshes to arbitrary levels before synchronization between submeshes and without the need of a central coordinator process for managing new vertices. Using the concept of canonical refinement, a simple proof of the independence of the resulting mesh on the mesh partitioning is given, which is useful in better understanding the behaviour of the biseetioning refinement procedure.

Adaptive grid methods are established as valuable computational technique in approximating effectively the solutions of problems with boundary or interior layers. In this paper, we present the analysis of an upwind scheme for singularly perturbed differential-difference equation on a grid which is formed by equidistributing arc-length monitor function. It is shown that the discrete solution obtained converges uniformly with respect to the perturbation parameter. Numerical experiments illustrate in practice the result of convergence proved theoretically.

In this paper, we propose a compound algorithm for the image restoration. The algorithm is a convex combination of the ROF model and the LLT model with a parameter function 0. The numerical experiments demonstrate that our compound algorithm is efficient and preserves the main advantages of the two models. In particular, the errors of the compound algorithm in L2 norm between the exact images and corresponding restored images are the smallest among the three models. For images with strong noises, the restored images of the compound algorithm are the best in the corresponding restored images. The proposed algorithm combines the fixed point method, an improved AMG method and the Krylov acceleration. It is found that the combination of these methods is efficient and robust in the image restoration.

In this paper we give an overview of the present state of fast solvers for the solution of the incompressible Navier-Stokes equations discretized by the finite element method and linearized by Newton or Picard＇s method. It is shown that block preconditioners form an excellent approach for the solution, however if the grids are not to fine preconditioning with a Saddle point ILU matrix （SILU） may be an attractive alternative. The applicability of all methods to stabilized elements is investigated. In case of the stand-alone Stokes equations special preconditioners increase the efficiency considerably.

We consider a finite difference scheme for a nonlinear wave equation, whose solutions may lose their smoothness in finite time, i.e., blow up in finite time. In order to numerically reproduce blow-up solutions, we propose a rule for a time-stepping,which is a variant of what was successfully used in the case of nonlinear parabolic equations. A numerical blow-up time is defined and is proved to converge, under a certain hypothesis, to the real blow-up time as the grid size tends to zero.

In this paper we study the computational performance of variants of an algebraic additive Schwarz preconditioner for the Schur complement for the solution of large sparse linear systems. In earlier works, the local Schur complements were computed exactly using a sparse direct solver. The robustness of the preconditioner comes at the price of this memory and time intensive computation that is the main bottleneck of the approach for tackling huge problems. In this work we investigate the use of sparse approximation of the dense local Schur complements. These approximations are computed using a partial incomplete LU factorization. Such a numerical calculation is the core of the multi-level incomplete factorization such as the one implemented in pARMS. The numerical and computing performance of the new numerical scheme is illustrated on a set of large 3D convection-diffusion problems; preliminary experiments on linear systems arising from structural mechanics are also reported.

A convex variational formulation is proposed to solve multicomponent signal processing problems in Hilbert spaces. The cost function consists of a separable term, in which each component is modeled through its own potential, and of a coupling term, in which constraints on linear transformations of the components are penalized with smooth functionals. An algorithm with guaranteed weak convergence to a solution to the problem is provided. Various multicomponent signal decomposition and recovery applications are discussed.

We give here an overview of the orbital-flee density functional theory that is used for modeling atoms and molecules. We review typical approximations to the kinetic energy, exchange-correlation corrections to the kinetic and Hartree energies, and constructions of the pseudopotentials. We discuss numerical discretizations for the orbital-free methods and include several numerical results for illustrations.

This paper aims to develop a power penalty method for a linear parabolic variational inequality （VI） in two spatial dimensions governing the two-asset American option valuation. This method yields a two-dimensional nonlinear parabolic PDE containing a power penalty term with penalty constant λ〉 1 and a power parameter k 〉 0. We show that the nonlinear PDE is uniquely solvable and the solution of the PDE converges to that of the VI at the rate of order O（λ^-k/2）. A fitted finite volume method is designed to solve the nonlinear PDE, and some numerical experiments are performed to illustrate the usefulness of this method.

In this paper, we propose a discrepancy rule-based method to automatically choose the regularization parameters for total variation image restoration problems. The regularization parameters are adjusted dynamically in each iteration. Numerical results are shown to illustrate the performance of the proposed method.

The gas-kinetic theory based flux splitting method has been successfully proposed for solving one- and two-dimensional ideal magnetohydrodynamics by Xu et al.[J. Comput. Phys., 1999; 2000], respectively. This paper extends the kinetic method to solve three-dimensional ideal magnetohydrodynamics equations, where an adaptive parameter η is used to control the numerical dissipation in the flux splitting method.Several numerical examples are given to demonstrate that the proposed method can achieve high numerical accuracy and resolve strong discontinuous waves in three dimensional ideal MHD problems.

In this work we consider the problem of shape reconstruction from an unorganized data set which has many important applications in medical imaging, scientific computing, reverse engineering and geometric modelling. The reconstructed surface is obtained by continuously deforming an initial surface following the Partial Differential Equation (PDE)-based diffusion model derived by a minimal volume-like variational formulation. The evolution is driven both by the distance from the data set and by the curvature analytically computed by it. The distance function is computed by implicit local interpolants defined in terms of radial basis functions. Space discretization of the PDE model is obtained by finite co-volume schemes and semi-implicit approach is used in time/scale. The use of a level set method for the numerical computation of the surface reconstruction allows us to handle complex geometry and even changing topology,without the need of user-interaction. Numerical examples demonstrate the ability of the proposed method to produce high quality reconstructions. Moreover, we show the effectiveness of the new approach to solve hole filling problems and Boolean operations between different data sets.

We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation. We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges. The clipping itself is efficiently computed by identifying for each constrained edge the （connected） set of triangles whose dual Voronoi vertices are hidden by the constraint. The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.

In this paper, we study the electromagnetic scattering from a two dimensional large rectangular open cavity embedded in an infinite ground plane, which is modelled by Helmholtz equations. By introducing nonlocal transparent boundary conditions, the problem in the open cavity is reduced to a bounded domain problem. A hypersingular integral operator and a weakly singular integral operator are involved in the TM and TE cases, respectively A new second-order Toeplitz type approximation and a second-order finite difference scheme are proposed for approximating the hypersingular integral operator on the aperture and the Helmholtz in the cavity, respectively. The existence and uniqueness of the numerical solution in the TE case are established for arbitrary wavenumbers. A fast algorithm for the second-order approximation is proposed for solving the cavity model with layered media. Numerical results show the second-order accuracy and efficiency of the fast algorithm. More important is that the algorithm is easy to implement as a preconditioner for cavity models with more general media.

The gas-kinetic theory based flux splitting method has been successfully proposed for solving one- and two-dimensional ideal magnetohydrodynamics by Xu et al. [J. Comput. Phys., 1999; 2000], respectively. This paper extends the kinetic method to solve three-dimensional ideal magnetohydrodynamics equations, where an adaptive parameter eta is used to control the numerical dissipation in the flux splitting method. Several numerical examples are given to demonstrate that the proposed method can achieve high numerical accuracy and resolve strong discontinuous waves in three dimensional ideal MHD problems.

This paper is concerned with the Cauchy problem for the modified Helmholtz equation in an infinite strip domain 0 〈 x ≤ 1, y ∈R . The Cauchy data at x = 0 is given and the solution is then sought for the interval 0 〈 x ≤ 1. This problem is highly ill-posed and the solution （if it exists） does not depend continuously on the given data. In this paper, we propose a fourth-order modified method to solve the Cauchy prob- lem. Convergence estimates are presented under the suitable choices of regularization parameters and the a priori assumption on the bounds of the exact solution. Numerical implementation is considered and the numerical examples show that our proposed method is effective and stable.