×

Triangulation automatique d’un polyèdre en dimension N. (French) Zbl 0567.65083

Die Methode der finiten Elemente erfordert häufig die Triangulation des zugehörigen Variablenbereiches \(\Omega\). Dies kann bei hohen Genauigkeitsforderungen bereits bei zwei Variablen und erst recht bei mehr als zwei Variablen ein ernsthaftes Problem darstellen. Im Falle, daß \(\Omega\) ein Polyeder des d-dimensionalen Euklidischen Raumes ist, wird in der vorliegenden Arbeit ein automatisches Vorgehen zur günstigen Triangulierung, d.h. zur Konstruktion einer günstigen simplizialen Zerlegung von \(\Omega\) angegeben. Ausgehend von den Voronoi- Polyedern, die zu einer gegebenen endlichen Punktmenge aus \(\Omega\) gebildet werden, wird unter Berücksichtigung der im höherdimensionalen Fall auftretenden Ausartungen mit geometrischen Überlegungen eine Delaunay-Triangulation (dual zum Voronoi-Diagramm) durch Hinzunahme je eines Punktes gebildet. Bei gegebenem Polyeder \(\Omega\) wird zuerst zu den Ecken der Berandung eine Delaunay- Triangulation hergestellt. Die Konstruktion innerer Punkte zwecks Verfeinerung der Triangulation folgt einer Maximalforderung gewisser Volumina von Simplizes, ausgedrückt durch entsprechende Determinanten. Einige der verwendeten Prinzipien sind empirischer Natur. Sodann wird auf Möglichkeiten zur Regularisierung einer vorliegenden Delaunay- Triangulation hingewiesen. Die Arbeit enthält viele interessante Beispiele und geometrische Darstellungen. Die angegebene Methode besitzt Anwendungen auch auf folgende Probleme im \({\mathbb{R}}^ d:\) Die Bestimmung der konvexen Hülle einer Menge von n Punkten, die Berechnung des Volumens eines beliebigen Polyeders, die Bestimmung der Lage eines Punktes relativ zu einem gegebenen Polyeder und die automatische Erzeugung des Voronoi-Diagramms in der Euklidischen Metrik. Der Verf. betont, daß für die Dimensionen 2 und 3 ein gut arbeitendes FORTRAN-Programm erstellt wurde.
Reviewer: G.Meinardus

MSC:

65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65Yxx Computer aspects of numerical algorithms
52-04 Software, source code, etc. for problems pertaining to convex and discrete geometry
52A10 Convex sets in \(2\) dimensions (including convex curves)
52A15 Convex sets in \(3\) dimensions (including convex surfaces)
52Bxx Polytopes and polyhedra
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] Y BABUSKA et A K AZIZ, On the angle condition in the finite element method, Siam J Num Anal, Vol 13, n^\circ 2 (1976) Zbl0324.65046 MR455462 · Zbl 0324.65046
[2] M BERGER, Geometrie tome 3 convexes et polytopes, polyedres réguliers, aires et volumes, Fernand Nathan Paris (1978) Zbl0423.51001 · Zbl 0423.51001
[3] W BROSTAW, JP DUSSAULT et B L FOX, Construction of Vornot polyhedra, J Comp Phys 29 (1978), pp 81-92 Zbl0392.73097 MR510461 · Zbl 0392.73097
[4] J CARNET, Une methode heuristique de maillage dans le plan pour la mise en oeuvre des elements finis, These Paris (1978)
[5] J C CAVENDISH, Automatic triangulation of arbitrary planar domains for the finite element method, Int J Num Meth Engng 8 (1974) pp 679-696 Zbl0284.73045 · Zbl 0284.73045
[6] P G CIARLET, The finite element method for elliptic problems, North-Holland (1978) Zbl0383.65058 MR520174 · Zbl 0383.65058
[7] H S M COXETER, L FEW et C A ROGERS, Covering space with equal spheres, Mathematika 6(1959), pp 147-157 Zbl0094.35301 MR124821 · Zbl 0094.35301
[8] B DELAUNAY, Sur la sphère vide, Bul Acad Sci URSS Class Sci Nat (1934), pp 793-800 Zbl0010.41101 · Zbl 0010.41101
[9] W F EDDY, A new convex hull algorithm for planar sets, ACM TMS, vol 3, n^\circ 4 (1977), pp 398-403 Zbl0374.68036 · Zbl 0374.68036
[10] P J GREEN et R SIBSON, Computing Dirichlet tesselations in the plane, The Computer Journal, vol 21, n^\circ 2 (1977), pp 168-173 Zbl0377.52001 MR485467 · Zbl 0377.52001
[11] F HERMELINE, Une methode automatique de maillage en dimension n, These Paris (1980)
[12] D T LEE, Two-dimensional Voronot diagrams in Lp-Metric, J of the ACM, vol 27, n^\circ 4 (1980), pp 604-618 Zbl0445.68053 MR594689 · Zbl 0445.68053
[13] S NORDBECK et B RYSTEDT, Computer cartography point in polygon programs, Bit, 7 (1967), pp 39-64 Zbl0146.14902 · Zbl 0146.14902
[14] C S PESKIN, Lagrangian method for the Navier-Stokes equations, Communication non publiée
[15] F P PREPARATA et S J HONG, Convex hull of finite sets of points in two and three dimension, Comm of the ACM, vol 20, n^\circ 2 (1977), p 87 Zbl0342.68030 MR488985 · Zbl 0342.68030
[16] R SIBSON, Locally equiangular triangulations, Comp J , vol 21, n^\circ 3 (1977), p 243 MR507358
[17] W C THACKER, A brief review of techniques for generating irregular computational grids, Int J Num Met Engng, vol 15 (1980), pp 1335-1341 Zbl0438.76003 · Zbl 0438.76003
[18] P F WATSON, Computing the n-dimensional Delaunay tesselation with application to Voronot polytopes, The Computer Journal, vol 24, n^\circ 2 (1981) MR619577
[19] A BOWYER, Computing Dirichlet tesselations, The Computer Journal, vol 24, n^\circ 2 (1981) MR619576
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.