Approximating constrained tetrahedrizations
type: Item
instance of: scholarly article
title: Approximating constrained tetrahedrizations
zbMATH Open document ID: 0772.65099
DOI: 10.1016/0167-8396(93)90052-5
author: Carol Hazlewood
published in: Computer Aided Geometric Design
publication date: 1993-05-16T00:00:00Z
review text: It was shown by \textit{E. Schönhardt} [Mat. Ann. 89, 309-312 (1927; JFM 53.0576.01)] that it is not always possible to turn a given set of points in \(\mathbb{R}^ 3\) into the vertices of a pseudo-manifold simplicial complex and such that a preassigned triangle should appear as a face in the complex. In computer aided design one has the additional problem that one would like to work with Delaunay triangulations for which many procedures are available. \textit{A. K. Cline} and \textit{R. J. Renka} [SIAM J. Numer. Anal. 27, No. 5, 1305-1321 (1990; Zbl 0714.65024)] relaxed the definition of a Delaunay triangulation in the case of two-dimensional problems to give an algorithm that allows the incorporation of pre-assigned segments. The author shows that a three-dimensional analogue of the Cline and Renka definition also leads to problems without solution. She therefore relaxes the conditions still more to obtain an explicit procedure that from a (Delaunay) triangulation \(T'\) of a pointset \(P'\) and a finite collection \(R\) of planar convex polygonal regions returns a set \(P\) and triangulation \(T\) of \(P\) such that \(P\setminus P' \in R\), \(T\) coincides with \(T'\) except for tetrahedra that are intersected (but not in face) by a region in \(R\) and any polygon in \(R\) is the union of faces of tetrahedra in \(T\). The procedure is linear in the number of tetrahedra in \(T'\) but exponential in the number of members of \(R\).
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65D17
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68U07
zbMATH DE Number: 166486
zbMATH Keywords: tetrahedrization
zbMATH Keywords: computational geometry
zbMATH Keywords: pseudo-manifold simplicial complex
zbMATH Keywords: computer aided design
zbMATH Keywords: Delaunay triangulations
zbMATH Keywords: algorithm
reviewed by: Heinrich Guggenheimer
describes a project that uses: Algorithm 624
MaRDI profile type: Publication
full work available at URL: 0167-8396(93)90052-5
OpenAlex ID: W2076027724
cites work: A discrete \(C^ 1\) interpolant for tetrahedral data
cites work: Three- and four-dimensional surfaces
cites work: A Constrained Two-Dimensional Triangulation and the Solution of Closest Node Problems in the Presence of Barriers
cites work: Tetrahedrizing point sets in three dimensions
cites work: Triangulation automatique d’un polyèdre en dimension $N$
cites work: Delaunay Triangular Meshes in Convex Polygons
cites work: Triangular meshes for regions of complicated shape
cites work: Properties of \(n\)-dimensional triangulations
cites work: Q3799261
cites work: \(C^ 1\) trivariate polynomial interpolation
cites work: Delaunay triangulation of arbitrarily shaped planar domains
Recommended article: Construction of three-dimensional Delaunay triangulations using local transformations
Recommended article: Delaunay's mesh of a convex polyhedron in dimension d. application to arbitrary polyhedra
Recommended article: OPTIMAL DELAUNAY POINT INSERTION
Recommended article: Q4878751
Recommended article: Conforming Delaunay triangulations in 3D
Recommended article: Fast Delaunay triangulation in three dimensions
Recommended article: Realizability of Delaunay triangulations
Recommended article: An optimal algorithm for realizing a Delaunay triangulation
description: scientific article; zbMATH DE number 166486