Computations of delaunay and higher order triangulations, with applications to splines

摘要: Digital data that consist of discrete points are frequently captured and processed by scientific engineering applications. Due to the rapid advance new gathering technologies, set sizes increasing, distributions becoming more irregular. These trends call for computational tools both efficient enough handle large sets flexible accommodate irregularity. A mathematical foundation is well-suited developing such triangulation, which can be defined point with little assumption about their distribution. The potential benefits from using triangulation not fully exploited. challenges fundamentally stem complexity structure, generally takes space represent than input points. This makes a program delicate task, particularly when it important runs fast robustly over data. This thesis addresses these in two parts. first part concentrates on techniques designed efficiently computing Delaunay triangulations three kinds practical data: terrain LIDAR sensors commonly found GIS, atom coordinate used biological applications, time varying volume generated simulations. The second problem defining spline spaces dimensions. It does so generalizing configurations, as follows. For given P dimensions, configuration pair subsets (T,I ) P, where T, called boundary set, triplet I, interior fall circumcircle through T. size degree configuration. As recently discovered Neamtu (2004), chosen all k configurations associated k+1 splines form basis space. In particular, trivial case k=0, coincides PL interpolation functions triangulation. Neamtu's definition relies only few structural properties configurations. raises question whether there exist other identical properties. If are, then configurations—let us them generalized hereon—can substituted thereby yielding family same set.