Transforming triangulations in polygonal domains

DOI10.1016/0167-8396(93)90029-3MaRDI QIDQ1315799zbMATH OpenOpenAlexWikidataFDO

Authors Ifat Goren, Nira Dyn, Samuel Rippa

Publication date 9 February 1995

Published in Computer Aided Geometric Design (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8396(93)90029-3

zbMATH Keywords

algorithmcomputational geometryfinite element methodspolygonal domainscattered data interpolationtransformationtriangulations

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Triangulations of a polygonal domain in the plane are the basic for many algorithms in the fields of finite element methods, scattered data interpolation, computational geometry etc. The efficiency of such algorithms frequently depends on the special triangulation. The authors prove that it is possible to transform every triangulation of a set of points inside a polygonal domain in the plane into every other triangulation of the same set of points using only operations of swapping diagonals in convex quadrilaterals. With the aid of this result it is possible to construct an algorithm to improve any initial triangulation with respect to a given criterion.

Recommendations

• Transforming triangulations on nonplanar surfaces
• Transforming pseudo-triangulations
• scientific article; zbMATH DE number 2009873
• Regularizing transformations of polygons
• Delaunay transformations of a Delaunay polytope
• scientific article; zbMATH DE number 3905323
• scientific article; zbMATH DE number 1786515
• Polygons and iteratively regularizing affine transformations
• Diagonal transformations of triangulation on surfaces
• Transforming plane triangulations by simultaneous diagonal flips

Cites work

• Data Dependent Triangulations for Piecewise Linear Interpolation
• Finite element mesh generation methods: A review and classification
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4022458 (Why is no real title available?)
• scientific article; zbMATH DE number 4028826 (Why is no real title available?)
• scientific article; zbMATH DE number 3633698 (Why is no real title available?)
• Transforming triangulations

Cited in

(7)

• Scattered data interpolation using minimum energy Powell-Sabin elements and data dependent triangulations
• Data-dependent triangulations for scattered data interpolation and finite element approximation
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Flip paths between lattice triangulations
• Computing optimal triangulations using simulated annealing
• All triangulations are reachable via sequences of edge-flips: an elementary proof
• Flip distance between two triangulations of a point set is NP-complete

This page was built for publication: Transforming triangulations in polygonal domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1315799)