0xDE (11011110) wrote,

Diamonds, kites, and circle packings

My paper "Diamond-Kite Meshes: Adaptive Quadrilateral Meshing and Orthogonal Circle Packing" just appeared on the arXiv as arXiv:1207.5082; it will be published in the 21st International Meshing Roundtable this October.

It's about a kind of quadrilateral mesh that you can make by starting with the rhombille tiling (a tiling of the plane by 60° rhombi that is also called "tumbling blocks" because of its resemblance to a pile of cubes) and overlaying copies of the same tiling, rotated by 90° and reduced in size by a factor of √3.



As well as having the usual properties that you'd want a finite element mesh to have (bounded aspect ratio elements, easy generation by repeated refinement, optimal number of elements for a given set of constraints on element sizes, etc) it has one much more unusual property: its vertices are the centers of the circles in a circle packing:



This is one of two types of packing guaranteed to exist by the Koebe–Andreev–Thurston circle packing theorem, in which a 3-connected planar graph and its dual are represented by circles so that adjacent vertices in either graph correspond to tangent circles and adjacent vertex-face pairs correspond to perpendicular circles (the other type involves only one graph, which should be maximal planar). In either of these two cases, the packing is essentially fixed by the graph, making its geometry hard to control: small local changes to the underlying graph can make the geometric shape of the circle packing very different. But these diamond-kite meshes turn that relation around, making the graph a function of the geometry rather than vice versa and allowing arbitrary amounts of subdivision in some regions of the plane without any change to the mesh in other parts of the plane that are far enough away.
Tags: circles, computational geometry, papers, quadrilaterals
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 3 comments