Quadrilateral meshes for PSLGs

DOI10.1007/S00454-016-9771-9MaRDI QIDQ306496zbMATH 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.10074

zbMATH Keywords

polynomial timeconforming meshesdissectionsnonobtuse triangulationoptimal angle boundsquadrilateral meshessinks

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 prove that every planar straight line graph with $n$ vertices has a conforming quadrilateral mesh with $O(n^2)$ elements, all angles $leq120^{c}irc$ and all new angles $geq60^{c}irc$. Both the complexity and the angle bounds are sharp. Moreover, all but $O(n)$ of the angles may be taken in a smaller interval, say $[89^{c}irc,91^{c}irc]$.

Recommendations

• Nonobtuse triangulations of PSLGs
• QUADRILATERAL MESHING BY CIRCLE PACKING
• CONSTRAINED QUADRILATERAL MESHES OF BOUNDED SIZE
• Small strictly convex quadrilateral meshes of point sets
• Improved approximations for minimum cardinality quadrangulations of finite element meshes

Cites work

• scientific article; zbMATH DE number 2174317 (Why is no real title available?)
• Conformal mapping in linear time
• Faster Circle Packing with Application to Nonobtuse Triangulation
• Linear-size nonobtuse triangulation of polygons
• Nonobtuse triangulations of PSLGs
• Optimal angle bounds for quadrilateral meshes
• QUADRILATERAL MESHING BY CIRCLE PACKING

Cited in

(3)

• QUADRILATERAL MESHING BY CIRCLE PACKING
• Nonobtuse triangulations of PSLGs
• Uniformly acute triangulations of PSLGs

This page was built for publication: Quadrilateral meshes for PSLGs

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