Quadrilateral Meshes for PSLGs

Christopher J. Bishop

doi:10.1007/s00454-016-9771-9

Quadrilateral Meshes for PSLGs

Christopher J. Bishop

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

We prove that every planar straight line graph with n vertices has a conforming quadrilateral mesh with O(n²) elements, all angles ≤ 120^∘ and all new angles ≥ 60^∘. Both the complexity and the angle bounds are sharp.

Original language	English
Pages (from-to)	1-42
Number of pages	42
Journal	Discrete and Computational Geometry
Volume	56
Issue number	1
DOIs	https://doi.org/10.1007/s00454-016-9771-9
State	Published - Jul 1 2016

Keywords

Conforming meshes
Dissections
Nonobtuse triangulation
Optimal angle bounds
Polynomial time
Quadrilateral meshes
Sinks

Access to Document

10.1007/s00454-016-9771-9

Cite this

@article{3fa4019643594e469b59aba3ffe3e5cb,

title = "Quadrilateral Meshes for PSLGs",

abstract = "We prove that every planar straight line graph with n vertices has a conforming quadrilateral mesh with O(n2) elements, all angles ≤ 120∘ and all new angles ≥ 60∘. Both the complexity and the angle bounds are sharp.",

keywords = "Conforming meshes, Dissections, Nonobtuse triangulation, Optimal angle bounds, Polynomial time, Quadrilateral meshes, Sinks",

author = "Bishop, \{Christopher J.\}",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2016",

month = jul,

day = "1",

doi = "10.1007/s00454-016-9771-9",

language = "English",

volume = "56",

pages = "1--42",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

number = "1",

}

TY - JOUR

T1 - Quadrilateral Meshes for PSLGs

AU - Bishop, Christopher J.

PY - 2016/7/1

Y1 - 2016/7/1

N2 - We prove that every planar straight line graph with n vertices has a conforming quadrilateral mesh with O(n2) elements, all angles ≤ 120∘ and all new angles ≥ 60∘. Both the complexity and the angle bounds are sharp.

AB - We prove that every planar straight line graph with n vertices has a conforming quadrilateral mesh with O(n2) elements, all angles ≤ 120∘ and all new angles ≥ 60∘. Both the complexity and the angle bounds are sharp.

KW - Conforming meshes

KW - Dissections

KW - Nonobtuse triangulation

KW - Optimal angle bounds

KW - Polynomial time

KW - Quadrilateral meshes

KW - Sinks

UR - https://www.scopus.com/pages/publications/84961169468

U2 - 10.1007/s00454-016-9771-9

DO - 10.1007/s00454-016-9771-9

M3 - Article

AN - SCOPUS:84961169468

SN - 0179-5376

VL - 56

SP - 1

EP - 42

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Quadrilateral Meshes for PSLGs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this