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

Author:
Marian Neamtu

Journal:
Trans. Amer. Math. Soc. **359** (2007), 2993-3004

MSC (2000):
Primary 41A15, 41A63; Secondary 05B45, 52C22, 65D17, 65D18

Published electronically:
February 8, 2007

MathSciNet review:
2299443

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**1.**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**, 10.1007/BF01228508**2.**Carl de Boor,*Splines as linear combinations of 𝐵-splines. A survey*, Approximation theory, II (Proc. Internat. Sympos., Univ.#Texas, Austin, Tex., 1976) Academic Press, New York, 1976, pp. 1–47. MR**0467092****3.**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**0218800****4.**Wolfgang Dahmen and Charles A. Micchelli,*Statistical encounters with 𝐵-splines*, Function estimates (Arcata, Calif., 1985) Contemp. Math., vol. 59, Amer. Math. Soc., Providence, RI, 1986, pp. 17–48. MR**870446**, 10.1090/conm/059/870446**5.**Wolfgang Dahmen, Charles A. Micchelli, and Hans-Peter Seidel,*Blossoming begets 𝐵-spline bases built better by 𝐵-patches*, Math. Comp.**59**(1992), no. 199, 97–115. MR**1134724**, 10.1090/S0025-5718-1992-1134724-1**6.**Delaunay, B., Sur la sphère vide, Bull. Acad. Sci. USSR (VII), Classe Sci. Mat. Nat., 1934, 793-800.**7.**Der Tsai Lee,*On 𝑘-nearest neighbor Voronoĭ diagrams in the plane*, IEEE Trans. Comput.**31**(1982), no. 6, 478–487. MR**669964**, 10.1109/TC.1982.1676031**8.**Charles A. Micchelli,*A constructive approach to Kergin interpolation in 𝑅^{𝑘}: multivariate 𝐵-splines and Lagrange interpolation*, Rocky Mountain J. Math.**10**(1980), no. 3, 485–497. MR**590212**, 10.1216/RMJ-1980-10-3-485**9.**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****10.**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****11.**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****12.**Franco P. Preparata and Michael Ian Shamos,*Computational geometry*, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR**805539****13.**Lyle Ramshaw,*Blossoms are polar forms*, Comput. Aided Geom. Design**6**(1989), no. 4, 323–358. MR**1030618**, 10.1016/0167-8396(89)90032-0**14.**Malcolm Sabin,*Open questions in the application of multivariate 𝐵-splines*, Mathematical methods in computer aided geometric design (Oslo, 1988), Academic Press, Boston, MA, 1989, pp. 529–537. MR**1022732**, 10.1016/B978-0-12-460515-2.50042-1**15.**Larry L. Schumaker,*Spline functions: basic theory*, John Wiley & Sons, Inc., New York, 1981. Pure and Applied Mathematics; A Wiley-Interscience Publication. MR**606200****16.**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.**17.**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**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
41A15,
41A63,
05B45,
52C22,
65D17,
65D18

Retrieve articles in all journals with MSC (2000): 41A15, 41A63, 05B45, 52C22, 65D17, 65D18

Additional Information

**Marian Neamtu**

Affiliation:
Department of Mathematics, Center for Constructive Approximation, Vanderbilt University, Nashville, Tennessee 37240

Email:
neamtu@math.vanderbilt.edu

DOI:
http://dx.doi.org/10.1090/S0002-9947-07-03976-1

Keywords:
Delaunay configuration,
Delaunay triangulation,
higher-order Voronoi diagram,
multivariate spline,
polynomial reproduction,
simplex spline

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.

Article copyright:
© Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.