Splines Over Iterated Voronoi Diagrams

样条曲线被用来描述几何对象，它可以被分解成单个的部分，从而保证这些部分的整体光滑性。 花键广泛用于汽车、航空航天和其他工程学科。 当几何体具有直线结构（例如汽车的车顶）时，它们工作得很好，但当不是这种情况时，需要相当大的努力。 由于这个原因，样条在生物或医学应用中使用不多，其中形状往往是高度不规则的。 这项研究介绍了一类新的样条具有所有的光滑性能的标准，但也能够科普复杂和非结构化的形状。 这项研究探索了一种新的类样条，那些定义在一组非结构化的2D点-即，假定没有规则结构。 B样条曲线理论中最基本的算法是递归de Boor算法。 该算法被推广到一个递归算法，涉及到在平面上的Voronoi图的层次结构的建设。 所得到的曲面是任意次数的，并且是分段光滑的。 它们能够再现任何阶的多项式。 由于de Boor算法是所有样条理论的基础，因此对非结构化点集进行适当的重新表述是一个重大突破，构成了本研究的主要智力价值。 定义在非结构化点集上的样条的存在开辟了处理复杂形状的可能性。 这对于有机形状尤其重要，因为有机形状往往非常不规则。 因此，这项研究的更广泛的影响是使用类似于标准样条的技术成功描述非工程形状的可能性。

ABSTRACT 0306385Farin, Gerald Arizona State UniversitySplines are used to describe geometric objects by breaking down into individual parts such that the overall smoothness of thes pieces is guaranteed. Splines are widely used in the automotive, aerospace, and other engineering disciplines. They work very well when the geometry has a rectilinear struture (such as the roof of a car), but need considerable effort when this is not the case. For that reason, splines are not much used in biological or medical applications, where shapes tend to be highly irregular. This research introduces a new class of splines having all the smoothness properties of standard ones but also being able to cope with complex and unstructured shapes. This research explores a new class splines, those that are defined over an unstructured set of 2D points - i.e., no regular structure is assumed. The most fundamental algorithm in the theory of B-spline curves is the recursive de Boor algorithm. This algorithm is generalized to a recursive algorithm involving the construction of a hierarchy of Voronoi diagrams in the plane. The resulting surfaces are of arbitrary degree and are piecewise smooth. They are capable of reproducing polynomials of any order. Since the de Boor Algorithm is fundamental to all spline theory, a proper reformulation for unstructured point sets is a significant breakthrough and constitutes the main intellectual merit of this research. The existence of splines defined over unstructured point sets opens up the possibility of handling complex shapes. This is particularly important for organic shapes, which tend to be highly irregular. Thus the broader impact of this research is the possibility to successfully describe non-engineering shapes using techniques similar to standard splines.