Nonobtuse triangulations of PSLGs

DOI10.1007/S00454-016-9772-8MaRDI QIDQ306497zbMATH OpenOpenAlexFDO

Authors Christopher J. Bishop

Publication date 31 August 2016

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Delaunay triangulationsGabriel conditionnonobtuse triangulationsthick/thin decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Abstract: We show that any planar straight line graph (PSLG) with $n$ vertices has a conforming triangulation by $O(n^{2.5})$ nonobtuse triangles (all angles $leq90^{c}irc$), answering the question of whether any polynomial bound exists. A nonobtuse triangulation is Delaunay, so this result also improves a previous $O(n^3)$ bound of Eldesbrunner and Tan for conforming Delaunay triangulations of PSLGs. In the special case that the PSLG is the triangulation of a simple polygon, we will show that only $O(n^2)$ triangles are needed, improving an $O(n^4)$ bound of Bern and Eppstein. We also show that for any $epsilon>0$, every PSLG has a conforming triangulation with $O(n^2/epsilo{n}^2)$ elements and with all angles bounded above by $90^{c}irc+epsilon$. This improves a result of S. Mitchell when $epsilon=3pi/8=67.5^{c}irc$ and Tan when $epsilon=7pi/30=42^{c}irc$.

Recommendations

• POLYNOMIAL-SIZE NONOBTUSE TRIANGULATION OF POLYGONS
• Acute and nonobtuse triangulations of polyhedral surfaces
• Linear-size nonobtuse triangulation of polygons
• TRIANGULATING POLYGONS WITHOUT LARGE ANGLES
• Acute triangulations of polygons

Cites work

• scientific article; zbMATH DE number 437532 (Why is no real title available?)
• scientific article; zbMATH DE number 3160754 (Why is no real title available?)
• scientific article; zbMATH DE number 53528 (Why is no real title available?)
• scientific article; zbMATH DE number 1795894 (Why is no real title available?)
• scientific article; zbMATH DE number 2164719 (Why is no real title available?)
• scientific article; zbMATH DE number 2098555 (Why is no real title available?)
• scientific article; zbMATH DE number 1424294 (Why is no real title available?)
• scientific article; zbMATH DE number 5239206 (Why is no real title available?)
• scientific article; zbMATH DE number 2227463 (Why is no real title available?)
• A dihedral acute triangulation of the cube
• A discrete Laplace-Beltrami operator for simplicial surfaces
• About Delaunay triangulations and discrete maximum principles for the linear conforming FEM applied to the Poisson equation.
• Acute and nonobtuse triangulations of polyhedral surfaces
• Acute triangulations of doubly covered convex quadrilaterals
• Acute triangulations of flat Möbius strips
• Acute triangulations of flat tori
• Acute triangulations of polygons
• Acute triangulations of polygons
• Acute triangulations of polyhedra and \(\mathbb R^N\)
• Acute triangulations of sphere and icosahedron
• Acute triangulations of the regular dodecahedral surface
• Acute triangulations of the regular icosahedral surface
• Adaptive spacetime meshing for discontinuous Galerkin methods
• An optimal bound for high-quality conforming triangulations
• An upper bound for conforming Delaunay triangulations
• Delaunay refinement algorithms for triangular mesh generation
• Drawing the planar dual
• Fast Marching Methods
• Linear-size nonobtuse triangulation of polygons
• Maximum principle and uniform convergence for the finite element method
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Nonobtuse triangulation of polygons
• Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains
• On Nonobtuse Simplicial Partitions
• PITCHING TENTS IN SPACE-TIME: MESH GENERATION FOR DISCONTINUOUS GALERKIN METHOD
• POLYNOMIAL-SIZE NONOBTUSE TRIANGULATION OF POLYGONS
• Point placement algorithms for Delaunay triangulation of polygonal domains
• Provably good mesh generation
• Quadrilateral meshes for PSLGs
• Quality Triangulations with Locally Optimal Steiner Points
• Solving elliptic finite element systems in near-linear time with support preconditioners
• Spacetime meshing with adaptive refinement and coarsening
• Stable Finite Elements for Problems with Wild Coefficients
• Survey of two-dimensional acute triangulations
• TRIANGULATING POLYGONS WITHOUT LARGE ANGLES
• The dissection of a polygon into nearly equilateral triangles
• There is no face-to-face partition of R^5 into acute simplices
• Well-centered triangulation

Cited in

(7)

• Uniformly acute triangulations of polygons
• POLYNOMIAL-SIZE NONOBTUSE TRIANGULATION OF POLYGONS
• Quadrilateral meshes for PSLGs
• Uniformly acute triangulations of PSLGs
• Edge-unfolding nearly flat convex caps
• scientific article; zbMATH DE number 2052963 (Why is no real title available?)
• Construction and Local Routing for Angle-Monotone Graphs

Describes a project that uses

Uses Software

• Triangle

This page was built for publication: Nonobtuse triangulations of PSLGs

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