Properties of \(n\)-dimensional triangulations. (English) Zbl 0624.65018

This paper establishes a number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplicial tesselation of the convex hull of an arbitrary finite set of points in n-space. The principal results of the present paper are (a) A set of \(n+2\) points in n-space may be triangulated in at most 2 different ways. (b) The ‘sphere test’ defined in this paper selects a preferred one of these two triangulations. (c) A set of parameters is defined that permits the characterization and enumeration of all sets of \(n+2\) points in n-space that are significantly different from the point of view of their possible triangulations. (d) The local sphere test induces a global sphere test property for a triangulation. (e) A triangulation satisfying the global sphere property is dual to the n-dimensional Dirichlet tesselation, i.e., it is a Delaunay triangulation.


65D99 Numerical approximation and computational geometry (primarily algorithms)
05B45 Combinatorial aspects of tessellation and tiling problems
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
Full Text: DOI


[1] Akima, H.; Akima, H., A method of bivariate interpolation and smooth surface Fitting for irregularly distributed data points, ACM trans. math. software, Algorithm, 526, 160-164, (1978), also · Zbl 0387.65010
[2] Barnhill, R.E.; Little, F.F., Three- and four-dimensional surfaces, Rocky mountain J. math., 14, 77-102, (1984) · Zbl 0552.65008
[3] Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 162-166, (1981)
[4] Cline, A.K.; Renka, R.L., A storage-efficient method for construction of a thiessen triangulation, Rocky mountain J. math., 14, 119-140, (1984) · Zbl 0568.65005
[5] Grandine, T.A., The stable evaluation of multivariate B-splines, (), 14
[6] Green, P.J.; Sibson, R., Computing Dirichlet tessellations in the plane, Comput. J., 21, 168-173, (1978) · Zbl 0377.52001
[7] Lawson, C.L., Generation of a triangular grid with application to contour plotting, Jet propulsion laboratory internal technical memorandum no. 299, (1972), Pasadena, CA
[8] Lawson, C.L., Software for C1 surface interpolation, (), 161-194
[9] Lawson, C.L., C1 surface interpolation for scattered data on a sphere, Rocky mountain J. math., 14, 177-202, (1984) · Zbl 0579.65008
[10] Renka, R.J.; Renka, R.J., Interpolation of data on the surface of a sphere, ACM trans. math. software, Algorithm, 623, 437-439, (1984), also · Zbl 0568.65006
[11] Renka, R.J., Algorithm 624. triangulation and interpolation of arbitrarily distributed points in the plane, ACM trans. math. software, 10, 440-442, (1984)
[12] Sibson, R., Locally equiangular triangulations, Comput. J., 21, 243-245, (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.