Small strictly convex quadrilateral meshes of point sets

DOI10.1007/S00453-003-1062-1zbMATH Open1072.68120arXivcs/0202011OpenAlexW2054150222MaRDI QIDQ1889600FDOQ1889600

Authors: David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán 

Publication date: 2 December 2004

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that $3lfloorfracn2floor$ internal Steiner points are always sufficient for a convex quadrilateral mesh of $n$ points in the plane. Furthermore, for any given $ngeq4$, there are point sets for which $lceilfracn-32ceil-1$ Steiner points are necessary for a convex quadrilateral mesh.

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

Recommendations

• scientific article; zbMATH DE number 2081026
• CONSTRAINED QUADRILATERAL MESHES OF BOUNDED SIZE
• Point sets with small integer coordinates and no large convex polygons
• scientific article; zbMATH DE number 2123350
• QUADRANGULAR REFINEMENTS OF CONVEX POLYGONS WITH AN APPLICATION TO FINITE-ELEMENT MESHES
• On Convex Quadrangulations of Point Sets on the Plane
• Quading triangular meshes with certain topological constraints
• Covering the convex quadrilaterals of point sets
• scientific article; zbMATH DE number 4060213

zbMATH Keywords

Steiner points

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (11)

• On Convex Quadrangulations of Point Sets on the Plane
• Computing convex quadrangulations
• Quadrilateral meshes for PSLGs
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• Title not available (Why is that?)
• Quadrangulations on 3-colored point sets with Steiner points and their winding numbers
• Convex quadrangulations of bichromatic point sets
• Small-size ε-nets for axis-parallel rectangles and boxes
• Low cardinality admissible meshes on quadrangles, triangles and disks
• Bichromatic quadrangulations with Steiner points
• CONSTRAINED QUADRILATERAL MESHES OF BOUNDED SIZE

This page was built for publication: Small strictly convex quadrilateral meshes of point sets

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