Affine invariant triangulations

DOI10.1016/J.CAGD.2021.102039zbMATH Open1480.65063arXiv2011.02197OpenAlexW3204744956MaRDI QIDQ2065637FDOQ2065637

Authors: Prosenjit Bose, Pilar Cano, Rodrigo I. Silveira 

Publication date: 12 January 2022

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

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$.

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

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• INTRINSIC MORPHING OF COMPATIBLE TRIANGULATIONS
• Title not available (Why is that?)
• Title not available (Why is that?)
• D3AdvM: A direct 3D adversarial sample attack inside mesh data
• Title not available (Why is that?)

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)