Algebraic Approximation of Large Data Set
Approximating large input data sets with a possibly complicated topology by one algebraic surface is not very efficient. In such cases a high degree surfaces would be necessary and as consequence additional unwanted branches of the surface might appear. It seems, that a use of piecewise techniques is more appropriate in this kind of situations. Two problems arise immediately. The first one is the geometry of the segmentation of the domain Ω. The second is the expression of the continuity on the common boundaries of segments.

The natural domains of interest of tensor product implicit patches are boxes. The space can be divided in a natural and symmetrical way in such boxes. We can for example use the division in the cubes of the same size. For the tensor-product functions the theory of B-splines basis functions, assuring the desired continuity, is simple and efficient.

In order to obtain the knot vectors, we consider a bounding box of the data, and subdivide a slightly enlarged area in cubic cells of constant size s. This subdivision induces an equidistant grid on the xy and z axis. Adding additional d  knots at the beginning and at the end of the grid, we obtain the knot vectors

• X=(ξi)i=1,...,m+1, Y=(ηj)j=1,...,n+1, and Z=(ξk)k=1,...,σ+1,
, As the B-spline basis function are locally polynomials of degree d  which are joined with d-1  continuity at the interior knot points, the products forming the basis Β  are locally tensor-product functions of degree (d,d,d) , which are joined with the d-1  continuity over the neighboring faces. A similar construction can be done if the three degrees of polynomials in x, y, z   directions are not the same.

We can also space the knots non-uniformally and even decrease the continuity at some faces by repeating the knots. But the described regular division into the cubes with the global d-1  continuity is the most simple, and leads to very good results for the most examples.

### Subset of tensor-product

The domain of interest Ω does not in fact need to contain all the cells within this grid. Obviously it has to contain the cells containing points. Additionally we consider neighboring cells. The reason for this is that the resulting surface is likely to pass through such a cell, and otherwise might be cut away. The basis B-spline functions vanish on the great number of knot intervals. Due to the restriction of on Ω, we only need to take the products of basis functions Mp(xNq(y) Op(z) into account that do not vanish on Ω. The indices are:

={(i,j,k) | ∃ l∈{1,...,n}, r ∈{1,...,m}, s∈{1,...,n}, t∈{1,...,σ}: Mr(pl,x) Ns(pl,y) Ot(pl,z) ≠ 0 ∧ max{|i-r|,|j-s|,|k-t|} ≤ 1}

We will therefore find the minimum of the functional only for the functions of the type

F = (i,j,k)∈ ci,j,k Mi(xNj(y) Ok(z).

Published June 24, 2005