Splines Over Iterated Voronoi Diagrams

亚利桑那州立大学杰拉尔德·法林用样条线来描述几何对象，将其分解成单独的部分，从而保证了这些部分的整体光滑性。花键广泛应用于汽车、航空航天和其他工程领域。当几何体具有直线结构(如车顶)时，它们工作得非常好，但当情况不是这样时，它们需要相当大的努力。出于这个原因，样条线在生物或医疗应用中使用不多，因为在这些应用中，形状往往非常不规则。这项研究介绍了一类新的样条线，它不仅具有标准样条线的所有光滑性，而且能够处理复杂和非结构化的形状。这项研究探索了一类新的样条线，它们定义在一组非结构化的二维点上，即不假定有规则的结构。B-Spline曲线理论中最基本的算法是递归De Boor算法。该算法被推广为一种递归算法，涉及构造平面上的Voronoi图的层次结构。得到的曲面是任意次数的，并且是分段光滑的。它们能够复制任何阶次的多项式。由于德布尔算法是所有样条理论的基础，对非结构化点集进行适当的重构是一个重大突破，也是本研究的主要智力价值所在。定义在非结构化点集上的样条线的存在使处理复杂形状成为可能。这对于有机形状尤其重要，因为有机形状往往非常不规则。因此，这项研究的更广泛的影响是有可能成功地使用类似于标准样条线的技术来描述非工程形状。

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.