## Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay

HTML articles powered by AMS MathViewer

- by Marian Neamtu PDF
- Trans. Amer. Math. Soc.
**359**(2007), 2993-3004 Request permission

## Abstract:

In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.## References

- Jean-Daniel Boissonnat, Olivier Devillers, and Monique Teillaud,
*A semidynamic construction of higher-order Voronoĭ diagrams and its randomized analysis*, Algorithmica**9**(1993), no. 4, 329–356. MR**1208566**, DOI 10.1007/BF01228508 - Carl de Boor,
*Splines as linear combinations of $B$-splines. A survey*, Approximation theory, II (Proc. Internat. Sympos., Univ. Texas, Austin, Tex., 1976) Academic Press, New York, 1976, pp. 1–47. MR**0467092** - H. B. Curry and I. J. Schoenberg,
*On Pólya frequency functions. IV. The fundamental spline functions and their limits*, J. Analyse Math.**17**(1966), 71–107. MR**218800**, DOI 10.1007/BF02788653 - Wolfgang Dahmen and Charles A. Micchelli,
*Statistical encounters with $B$-splines*, Function estimates (Arcata, Calif., 1985) Contemp. Math., vol. 59, Amer. Math. Soc., Providence, RI, 1986, pp. 17–48. MR**870446**, DOI 10.1090/conm/059/870446 - Wolfgang Dahmen, Charles A. Micchelli, and Hans-Peter Seidel,
*Blossoming begets $B$-spline bases built better by $B$-patches*, Math. Comp.**59**(1992), no. 199, 97–115. MR**1134724**, DOI 10.1090/S0025-5718-1992-1134724-1 - Delaunay, B., Sur la sphère vide, Bull. Acad. Sci. USSR (VII), Classe Sci. Mat. Nat., 1934, 793–800.
- Der Tsai Lee,
*On $k$-nearest neighbor Voronoĭ diagrams in the plane*, IEEE Trans. Comput.**31**(1982), no. 6, 478–487. MR**669964**, DOI 10.1109/TC.1982.1676031 - Charles A. Micchelli,
*A constructive approach to Kergin interpolation in $\textbf {R}^{k}$: multivariate $B$-splines and Lagrange interpolation*, Rocky Mountain J. Math.**10**(1980), no. 3, 485–497. MR**590212**, DOI 10.1216/RMJ-1980-10-3-485 - Charles A. Micchelli,
*Mathematical aspects of geometric modeling*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 65, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. MR**1308048**, DOI 10.1137/1.9781611970067 - Marian Neamtu,
*What is the natural generalization of univariate splines to higher dimensions?*, Mathematical methods for curves and surfaces (Oslo, 2000) Innov. Appl. Math., Vanderbilt Univ. Press, Nashville, TN, 2001, pp. 355–392. MR**1858970** - Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu,
*Spatial tessellations: concepts and applications of Voronoi diagrams*, 2nd ed., Wiley Series in Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 2000. With a foreword by D. G. Kendall. MR**1770006**, DOI 10.1002/9780470317013 - Franco P. Preparata and Michael Ian Shamos,
*Computational geometry*, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR**805539**, DOI 10.1007/978-1-4612-1098-6 - Lyle Ramshaw,
*Blossoms are polar forms*, Comput. Aided Geom. Design**6**(1989), no. 4, 323–358. MR**1030618**, DOI 10.1016/0167-8396(89)90032-0 - Malcolm Sabin,
*Open questions in the application of multivariate $B$-splines*, Mathematical methods in computer aided geometric design (Oslo, 1988) Academic Press, Boston, MA, 1989, pp. 529–537. MR**1022732**, DOI 10.1016/B978-0-12-460515-2.50042-1 - Larry L. Schumaker,
*Spline functions: basic theory*, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981. MR**606200** - Seidel, H.-P., Polar forms and triangular B-spline surfaces, in
*Blossoming: The New Polar-Form Approach to Spline Curves and Surfaces SIGGRAPH ’91*, Course Notes #26, ACM SIGGRAPH, 1991. - Michael Ian Shamos and Dan Hoey,
*Closest-point problems*, 16th Annual Symposium on Foundations of Computer Science (Berkeley, Calif., 1975) IEEE Computer Society, Long Beach, Calif., 1975, pp. 151–162. MR**0426498**

## Additional Information

**Marian Neamtu**- Affiliation: Department of Mathematics, Center for Constructive Approximation, Vanderbilt University, Nashville, Tennessee 37240
- Email: neamtu@math.vanderbilt.edu
- Received by editor(s): February 12, 2004
- Received by editor(s) in revised form: February 4, 2005
- Published electronically: February 8, 2007
- Additional Notes: This work was supported by the NSF under grant CCF-0204174.
- © Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**359**(2007), 2993-3004 - MSC (2000): Primary 41A15, 41A63; Secondary 05B45, 52C22, 65D17, 65D18
- DOI: https://doi.org/10.1090/S0002-9947-07-03976-1
- MathSciNet review: 2299443