Affine invariant triangulations

DOI10.1016/J.CAGD.2021.102039MaRDI QIDQ2065637zbMATHOpenAlexFDO

Authors Prosenjit Bose, Pilar Cano, Rodrigo I. Silveira

Publication date 12 January 2022

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

Full work available at URL https://arxiv.org/abs/2011.02197

zbMATH Keywords

triangulationsaffine invariantaffine invariant algorithmsaffine invariant norms

Mathematics Subject Classification ID

Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs (65M50) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Abstract: We study affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set $S$ for any (unknown) affine transformation of $S$. Our work is based on a method by Nielson [A characterization of an affine invariant triangulation. Geom. Mod, 191-210. Springer, 1993] that uses the inverse of the covariance matrix of $S$ to define an affine invariant norm, denoted $A_S$, and an affine invariant triangulation, denoted ${DT}_{A_S}[S]$. We revisit the $A_S$-norm from a geometric perspective, and show that ${DT}_{A_S}[S]$ can be seen as a standard Delaunay triangulation of a transformed point set based on $S$. We prove that it retains all of its well-known properties such as being 1-tough, containing a perfect matching, and being a constant spanner of the complete geometric graph of $S$. We show that the $A_S$-norm extends to a hierarchy of related geometric structures such as the minimum spanning tree, nearest neighbor graph, Gabriel graph, relative neighborhood graph, and higher order versions of these graphs. In addition, we provide different affine invariant sorting methods of a point set $S$ and of the vertices of a polygon $P$ that can be combined with known algorithms to obtain other affine invariant triangulation methods of $S$ and of $P$.

Recommendations

• scientific article; zbMATH DE number 917637
• Affine invariants of generalized polygons and matching under affine transformations
• scientific article; zbMATH DE number 4105506
• The geometric meaning of Nielson's affine invariant norm
• Affine invariant distance using multiscale analysis

Cites work

• scientific article; zbMATH DE number 4023930 (Why is no real title available?)
• scientific article; zbMATH DE number 140458 (Why is no real title available?)
• scientific article; zbMATH DE number 917637 (Why is no real title available?)
• A note on Delaunay and optimal triangulations
• An efficient algorithm for determining the convex hull of a finite planar set
• Characterizing and efficiently computing quadrangulations of planar point sets
• Delaunay graphs are almost as good as complete graphs
• Graham triangulations and triangulations with a center are Hamiltonean
• Location of a Point in a Planar Subdivision and Its Applications
• Methods for Euclidean geometry
• On shape Delaunay tessellations
• Polygons Have Ears
• The Oxford dictionary of statistical terms.
• The relative neighbourhood graph of a finite planar set
• The stretch factor of the Delaunay triangulation is less than 1.998
• Toughness and Delaunay triangulations
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Voronoi diagrams and Delaunay triangulations

Cited in

(6)

• scientific article; zbMATH DE number 4105506 (Why is no real title available?)
• INTRINSIC MORPHING OF COMPATIBLE TRIANGULATIONS
• scientific article; zbMATH DE number 1698729 (Why is no real title available?)
• scientific article; zbMATH DE number 917637 (Why is no real title available?)
• scientific article; zbMATH DE number 3570473 (Why is no real title available?)
• D3AdvM: A direct 3D adversarial sample attack inside mesh data

This page was built for publication: Affine invariant triangulations

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