Nonobtuse triangulations of PSLGs

DOI10.1007/S00454-016-9772-8zbMATH Open1348.68280arXiv2007.10041OpenAlexW989082841MaRDI QIDQ306497FDOQ306497

Authors: Christopher J. Bishop 

Publication date: 31 August 2016

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

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

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

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

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)

Cites Work

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

Cited In (7)

• Uniformly acute triangulations of polygons
• POLYNOMIAL-SIZE NONOBTUSE TRIANGULATION OF POLYGONS
• Edge-Unfolding Nearly Flat Convex Caps
• Quadrilateral meshes for PSLGs
• Uniformly acute triangulations of PSLGs
• Title not available (Why is that?)
• Construction and Local Routing for Angle-Monotone Graphs

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)