Quadrilateral meshing by circle packing

Authors
Bern, M Eppstein, D
Citation
M. Bern et D. Eppstein, Quadrilateral meshing by circle packing, INT J C GEO, 10(4), 2000, pp. 347-360
Citations number
18
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
10
Issue
4
Year of publication
2000
Pages
347 - 360
Database
ISI
SICI code
0218-1959(200008)10:4<347:QMBCP>2.0.ZU;2-3
Abstract
We use circle-packing methods to generate quadrilateral meshes for polygona l domains, with guaranteed bounds both on the quality and the number of ele ments. We show that these methods can generate meshes of several types: (1) the elements form the cells of a Voronoi diagram, (2) all elements have tw o opposite 90 degrees angles, (3) all elements are kites, or (4) all angles are at most 120 degrees. In each case the total number of elements is O(n) , where n is the number of input vertices.