Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay
Author:
Marian Neamtu
Journal:
Trans. Amer. Math. Soc. 359 (2007), 29933004
MSC (2000):
Primary 41A15, 41A63; Secondary 05B45, 52C22, 65D17, 65D18
Published electronically:
February 8, 2007
MathSciNet review:
2299443
Fulltext 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 socalled 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 socalled simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the wellknown univariate Bsplines. 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.
JeanDaniel
Boissonnat, Olivier
Devillers, and Monique
Teillaud, A semidynamic construction of higherorder
Voronoĭ\ diagrams and its randomized analysis, Algorithmica
9 (1993), no. 4, 329–356. MR 1208566
(94k:68182), http://dx.doi.org/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
(57 #6959)
 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
(36 #1884)
 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
(88d:65022), http://dx.doi.org/10.1090/conm/059/870446
 5.
Wolfgang
Dahmen, Charles
A. Micchelli, and HansPeter
Seidel, Blossoming begets 𝐵spline
bases built better by 𝐵patches, Math.
Comp. 59 (1992), no. 199, 97–115. MR 1134724
(93b:41014), http://dx.doi.org/10.1090/S00255718199211347241
 6.
Delaunay, B., Sur la sphère vide, Bull. Acad. Sci. USSR (VII), Classe Sci. Mat. Nat., 1934, 793800.
 7.
Der
Tsai Lee, On 𝑘nearest neighbor Voronoĭ\ diagrams in
the plane, IEEE Trans. Comput. 31 (1982), no. 6,
478–487. MR
669964 (83m:68157), http://dx.doi.org/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
(84i:41002), http://dx.doi.org/10.1216/RMJ1980103485
 9.
Charles
A. Micchelli, Mathematical aspects of geometric modeling,
CBMSNSF Regional Conference Series in Applied Mathematics, vol. 65,
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA,
1995. MR
1308048 (95i:65036)
 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 (2001c:52013)
 12.
Franco
P. Preparata and Michael
Ian Shamos, Computational geometry, Texts and Monographs in
Computer Science, SpringerVerlag, New York, 1985. An introduction. MR 805539
(87d:68102)
 13.
Lyle
Ramshaw, Blossoms are polar forms, Comput. Aided Geom. Design
6 (1989), no. 4, 323–358. MR 1030618
(91d:65026), http://dx.doi.org/10.1016/01678396(89)900320
 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
(90k:65050)
 15.
Larry
L. Schumaker, Spline functions: basic theory, John Wiley &
Sons, Inc., New York, 1981. Pure and Applied Mathematics; A
WileyInterscience Publication. MR 606200
(82j:41001)
 16.
Seidel, H.P., Polar forms and triangular Bspline surfaces, in Blossoming: The New PolarForm Approach to Spline Curves and Surfaces SIGGRAPH '91, Course Notes #26, ACM SIGGRAPH, 1991.
 17.
Michael
Ian Shamos and Dan
Hoey, Closestpoint problems, 16th Annual Symposium on
Foundations of Computer Science (Berkeley, Calif., 1975) IEEE Computer
Society, Long Beach, Calif., 1975, pp. 151–162. MR 0426498
(54 #14441)
 1.
 Boissonnat, J.D., O. Devillers, and M. Teillaud, A semidynamic construction of higherorder Voronoi diagrams and its randomized analysis, Algorithmica 9 (1993), 329356. MR 1208566 (94k:68182)
 2.
 Boor, C. de, Splines as linear combinations of Bsplines. A survey, in Approximation Theory, II, G. G. Lorentz, C. K. Chui, and L. L. Schumaker (eds.), Academic Press, New York, 1976, 147. MR 0467092 (57:6959)
 3.
 Curry, H. B., and I. J. Schoenberg, On Pólya frequency functions IV: The fundamental spline functions and their limits, J. Analyse Math. 17 (1966), 71107. MR 0218800 (36:1884)
 4.
 Dahmen, W., and C. A. Micchelli, Statistical encounters with Bsplines, in Function Estimates (Arcata, Calif., 1985), Contemp. Math., 59, Amer. Math. Soc., Providence, 1986, 1748. MR 0870446 (88d:65022)
 5.
 Dahmen, W., C. A. Micchelli, and H.P. Seidel, Blossoming begets Bsplines built better by Bpatches, Math. Comp. 59 (1992), 97115. MR 1134724 (93b:41014)
 6.
 Delaunay, B., Sur la sphère vide, Bull. Acad. Sci. USSR (VII), Classe Sci. Mat. Nat., 1934, 793800.
 7.
 Lee, D.T., On nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comp. 31 (1982), 478487. MR 0669964 (83m:68157)
 8.
 Micchelli, C. A., A constructive approach to Kergin interpolation in : multivariate Bsplines and Lagrange interpolation, Rocky Mountain J. Math. 10 (1980), 485497. MR 0590212 (84i:41002)
 9.
 Micchelli, C. A., Mathematical Aspects of Geometric Modeling, CBMSNSF Regional Conference Series in Applied Mathematics, 65, SIAM, Philadelphia, 1995. MR 1308048 (95i:65036)
 10.
 Neamtu, M., What is the natural generalization of univariate splines to higher dimensions?, in Mathematical Methods for Curves and Surfaces: Oslo 2000, T. Lyche and L. L. Schumaker (eds.), Vanderbilt University Press, Nashville, TN, 2001, 355392. MR 1858970
 11.
 Okabe, A., B. Boots, and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed., Wiley, Chichester, England, 2000. MR 1770006 (2001c:52013)
 12.
 Preparata, F. P., and M. I. Shamos, Computational Geometry, Springer, 1985. MR 0805539 (87d:68102)
 13.
 Ramshaw, L., Blossoms are polar forms, Comput. Aided Geom. Design 6 (1989), 323358. MR 1030618 (91d:65026)
 14.
 Sabin, M., Open questions in the application of multivariate Bsplines, in Mathematical Methods in Computer Aided Geometric Design, T. Lyche and L. L. Schumaker (eds.), Academic Press, New York, 1989, 529537. MR 1022732 (90k:65050)
 15.
 Schumaker, L. L., Spline Functions: Basic Theory, Interscience, New York, 1981. Reprinted by Krieger, Malabar, Florida, 1993. MR 0606200 (82j:41001)
 16.
 Seidel, H.P., Polar forms and triangular Bspline surfaces, in Blossoming: The New PolarForm Approach to Spline Curves and Surfaces SIGGRAPH '91, Course Notes #26, ACM SIGGRAPH, 1991.
 17.
 Shamos, M. I., and D. Hoey, Closestpoint problems, in IEEE Symposium on Foundations of Computer Science, 1975, 151162. MR 0426498 (54:14441)
Similar Articles
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/S0002994707039761
PII:
S 00029947(07)039761
Keywords:
Delaunay configuration,
Delaunay triangulation,
higherorder 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 CCF0204174.
Article copyright:
© Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
