Graphs, Kites and Darts
Non-periodic tilings with Penrose’s kites and darts
We continue our investigation of the tilings using Haskell with Haskell Diagrams. What is new is the introduction of a planar graph representation. This allows us to define more operations on finite tilings, in particular forcing and composing.
Previously in Diagrams for Penrose Tiles we implemented tools to create and draw finite patches of Penrose kites and darts (such as the samples depicted in figure 1). The code for this and for the new graph representation and tools described here can be found on GitHub https://github.com/chrisreade/PenroseKiteDart.
To describe the tiling operations it is convenient to work with the half-tiles: LD (left dart), RD (right dart), LK (left kite), RK (right kite) using a polymorphic type HalfTile (defined in a module HalfTile)
data HalfTile rep
= LD rep | RD rep | LK rep | RK rep deriving (Show,Eq)Here rep is a type variable for a representation to be chosen. For drawing purposes, we chose two-dimensional vectors (V2 Double) and called these Pieces.
type Piece = HalfTile (V2 Double)The vector represents the join edge of the half tile (see figure 2) and thus the scale and orientation are determined (the other tile edges are derived from this when producing a diagram).
Finite tilings or patches are then lists of located pieces.
type Patch = [Located Piece]Both Piece and Patch are made transformable so rotate, and scale can be applied to both and translate can be applied to a Patch. (Translate has no effect on a Piece unless it is located.)
In Diagrams for Penrose Tiles we also discussed the rules for legal tilings and specifically the problem of incorrect tilings which are legal but get stuck so cannot continue to infinity. In order to create correct tilings we implemented the decompose operation on patches.
The vector representation that we use for drawing is not well suited to exploring properties of a patch such as neighbours of pieces. Knowing about neighbouring tiles is important for being able to reason about composition of patches (inverting a decomposition) and to find which pieces are determined (forced) on the boundary of a patch.
However, the polymorphic type HalfTile allows us to introduce our alternative graph representation alongside Pieces.
Tile Graphs
In the module Tgraph.Prelude, we have the new representation which treats half tiles as triangular faces of a planar graph – a TileFace – by specialising HalfTile with a triple of vertices (clockwise starting with the tile origin). For example
LD (1,3,4) RK (6,4,3)type Vertex = Int
type TileFace = HalfTile (Vertex,Vertex,Vertex)When we need to refer to particular vertices from a TileFace we use originV (the first vertex – red dot in figure 2), oppV (the vertex at the opposite end of the join edge – dashed edge in figure 2), wingV (the remaining vertex not on the join edge).
originV, oppV, wingV :: TileFace -> VertexTgraphs
The Tile Graphs implementation uses a type Tgraph which has a list of graph vertices and a list of tile faces.
data Tgraph = Tgraph { vertices :: [Vertex]
, faces :: [TileFace]
} deriving (Show)For example, fool (short for a fool’s kite) is a Tgraph with 6 faces and 7 vertices, shown in figure 3.
fool = Tgraph { vertices = [1,2,3,4,5,6,7]
, faces = [RD (1,2,3),LD (1,3,4),RK (6,2,5)
,LK (6,3,2),RK (6,4,3),LK (6,7,4)
]
}(The fool is also called an ace in the literature)
With this representation we can investigate how composition works with whole patches. Figure 4 shows a twice decomposed sun on the left and a once decomposed sun on the right (both with vertex labels). In addition to decomposing the right graph to form the left graph, we can also compose the left graph to get the right graph.
After implementing composition, we also explore a force operation and an emplace operation to extend tilings.
There are some constraints we impose on Tgraphs.
- No spurious vertices. Every vertex of a
Tgraphface must be one of theTgraphvertices and each of theTgraphvertices occurs in at least one of theTgraphfaces. - Connected. The collection of faces must be a single connected component.
- No crossing boundaries. By this we mean that vertices on the boundary are incident with exactly two boundary edges. The boundary consists of the edges between the
Tgraphfaces and exterior region(s). This is important for adding faces. - Tile connected. Roughly, this means that if we collect the faces of a
Tgraphby starting from any single face and then add faces which share an edge with those already collected, we get all theTgraphfaces. This is important for drawing purposes.
In fact, if a Tgraph is connected with no crossing boundaries, then it must be tile connected. (We could define tile connected to mean that the dual graph excluding exterior regions is connected.)
Figure 5 shows two excluded graphs which have crossing boundaries at 4 (left graph) and 13 (right graph). The left graph is still tile connected but the right is not tile connected (the two faces at the top right do not have an edge in common with the rest of the faces.)
Although we have allowed for Tgraphs with holes (multiple exterior regions), we note that such holes cannot be created by adding faces one at a time without creating a crossing boundary. They can be created by removing faces from a Tgraph without necessarily creating a crossing boundary.
Important We are using face as an abbreviation for half-tile face of a Tgraph here, and we do not count the exterior of a patch of faces to be a face. The exterior can also be disconnected when we have holes in a patch of faces and the holes are not counted as faces either. In graph theory, the term face would generally include these other regions, but we will call them exterior regions rather than faces.
In addition to the constructor Tgraph we also use
checkedTgraph:: [TileFace] -> Tgraphwhich creates a Tgraph from a list of faces, but also performs checks on the required properties of Tgraphs. We can then remove or select faces from a Tgraph and then use checkedTgraph to ensure the resulting Tgraph still satisfies the required properties.
selectFaces, removeFaces :: [TileFace] -> Tgraph -> Tgraph
selectFaces fcs g = checkedTgraph (faces g `intersect` fcs)
removeFaces fcs g = checkedTgraph (faces g \\ fcs)Edges and Directed Edges
We do not explicitly record edges as part of a Tgraph, but calculate them as needed. Implicitly we are requiring
- No spurious edges. The edges of a
Tgraphare the edges of the faces of theTgraph.
To represent edges, a pair of vertices (a,b) is regarded as a directed edge from a to b. A list of such pairs will usually be regarded as a directed edge list. In the special case that the list is symmetrically closed [(b,a) is in the list whenever (a,b) is in the list] we will refer to this as an edge list rather than a directed edge list.
The following functions on TileFaces all produce directed edges (going clockwise round a face).
-- join edge - dashed in figure 2
joinE :: TileFace -> (Vertex,Vertex)
-- the short edge which is not a join edge
shortE :: TileFace -> (Vertex,Vertex)
-- the long edge which is not a join edge
longE :: TileFace -> (Vertex,Vertex)
-- all three directed edges clockwise from origin
faceDedges :: TileFace -> [(Vertex,Vertex)]For the whole Tgraph, we often want a list of all the directed edges of all the faces.
graphDedges :: Tgraph -> [(Vertex,Vertex)]
graphDedges g = concatMap faceDedges (faces g)Because our graphs represent tilings they are planar (can be embedded in a plane) so we know that at most two faces can share an edge and they will have opposite directions of the edge. No two faces can have the same directed edge. So from graphDedges g we can easily calculate internal edges (edges shared by 2 faces) and boundary directed edges (directed edges round the external regions).
internalEdges, boundaryDedges :: Tgraph -> [(Vertex,Vertex)]The internal edges of g are those edges which occur in both directions in graphDedges g. The boundary directed edges of g are the missing reverse directions in graphDedges g.
We also refer to all the long edges of a Tgraph (including kite join edges) as phiEdges (both directions of these edges).
phiEdges :: Tgraph -> [(Vertex, Vertex)]This is so named because, when drawn, these long edges are phi times the length of the short edges (phi being the golden ratio which is approximately 1.618).
Drawing Tgraphs (Patches and VPatches)
The module Tgraph.Convert contains functions to convert a Tgraph to our previous vector representation (Patch) defined in TileLib so we can use the existing tools to produce diagrams.
makePatch :: Tgraph -> Patch
drawPatch :: Patch -> Diagram B -- defined in module TileLib
drawGraph :: Tgraph -> Diagram B
drawGraph = drawPatch . makePatchHowever, it is also useful to have an intermediate stage (a VPatch = Vertex Patch) which contains both face (vertices) and vectors. This allows vertex labels to be drawn and for faces to be identified and retained/excluded after the vector information is calculated.
data VPatch = VPatch {lVertices :: [Located Vertex]
,lHybrids :: [Located Hybrid]
}A Vpatch has a list of located vertices and a list of located hybrids, where a Hybrid is a HalfTile with a dual representation of the face (vertices) and vector (join edge). We make VPatch transformable so it can also be an argument type for rotate, translate, and scale.
The conversion functions include
makeVPatch :: Tgraph -> VPatch
dropVertices :: VPatch -> Patch -- discards vertex information
drawVPatch :: VPatch -> Diagram B -- draws labels as well
drawVGraph :: Tgraph -> Diagram B
drawVGraph = drawVPatch . makeVPatchOne consequence of using abstract graphs is that there is no unique predefined way to orient or scale or position the patch arising from a graph representation. Our implementation selects a particular join edge and aligns it along the x-axis (unit length for a dart, philength for a kite) and tile-connectedness ensures the rest of the patch can be calculated from this.
We also have functions to re-orient a Vpatch and lists of VPatchs using chosen pairs of vertices. [Simply doing rotations on the final diagrams can cause problems if these include vertex labels. We do not, in general, want to rotate the labels – so we need to orient the Vpatch before converting to a diagram]
Decomposing Graphs
We previously implemented decomposition for patches which splits each half-tile into two or three smaller scale half-tiles.
decompose :: Patch -> PatchWe now have a Tgraph version of decomposition in the module Tgraphs:
decomposeG :: Tgraph -> TgraphGraph decomposition is particularly simple. We start by introducing one new vertex for each long edge (the phiEdges) of the Tgraph. We then build the new faces from each old face using the new vertices.
As a running example we take fool (mentioned above) and its decomposition foolD
*Main> foolD = decomposeG fool
*Main> foolD
Tgraph { vertices = [1,8,3,2,9,4,5,13,10,6,11,14,7,12]
, faces = [LK (1,8,3),RD (2,3,8),RK (1,3,9)
,LD (4,9,3),RK (5,13,2),LK (5,10,13)
,RD (6,13,10),LK (3,2,13),RK (3,13,11)
,LD (6,11,13),RK (3,14,4),LK (3,11,14)
,RD (6,14,11),LK (7,4,14),RK (7,14,12)
,LD (6,12,14)
]
}which are best seen together (fool followed by foolD) in figure 6.
Composing graphs, and Unknowns
Composing is meant to be an inverse to decomposing, and one of the main reasons for introducing our graph representation. In the literature, decomposition and composition are defined for infinite tilings and in that context they are unique inverses to each other. For finite patches, however, we will see that composition is not always uniquely determined.
In figure 7 (Two Levels) we have emphasised the larger scale faces on top of the smaller scale faces.
How do we identify the composed tiles? We start by classifying vertices which are at the wing tips of the (smaller) darts as these determine how things compose. In the interior of a graph/patch (e.g in figure 7), a dart wing tip always coincides with a second dart wing tip, and either
- the 2 dart halves share a long edge. The shared wing tip is then classified as a
largeKiteCentreand is at the centre of a larger kite. (See left vertex type in figure 8), or - the 2 dart halves touch at their wing tips without sharing an edge. This shared wing tip is classified as a
largeDartBaseand is the base of a larger dart. (See right vertex type in figure 8)
[We also call these (respectively) a deuce vertex type and a jack vertex type later in figure 10]
Around the boundary of a graph, the dart wing tips may not share with a second dart. Sometimes the wing tip has to be classified as unknown but often it can be decided by looking at neighbouring tiles. In this example of a four times decomposed sun (sunD4), it is possible to classify all the dart wing tips as largeKiteCentres or largeDartBases so there are no unknowns.
If there are no unknowns, then we have a function to produce the unique composed graph.
composeG:: Tgraph -> TgraphAny correct decomposed graph without unknowns will necessarily compose back to its original. This makes composeG a left inverse to decomposeG provided there are no unknowns.
For example, with an (n times) decomposed sun we will have no unknowns, so these will all compose back up to a sun after n applications of composeG. For n=4 (sunD4 – the smaller scale shown in figure 7) the dart wing classification returns 70 largeKiteCentres, 45 largeDartBases, and no unknowns.
Similarly with the simpler foolD example, if we classsify the dart wings we get
largeKiteCentres = [14,13]
largeDartBases = [3]
unknowns = []In foolD (the right hand graph in figure 6), nodes 14 and 13 are new kite centres and node 3 is a new dart base. There are no unknowns so we can use composeG safely
*Main> composeG foolD
Tgraph { vertices = [1,2,3,4,5,6,7]
, faces = [RD (1,2,3),LD (1,3,4),RK (6,2,5)
,RK (6,4,3),LK (6,3,2),LK (6,7,4)
]
}which reproduces the original fool (left hand graph in figure 6).
However, if we now check out unknowns for fool we get
largeKiteCentres = []
largeDartBases = []
unknowns = [4,2] So both nodes 2 and 4 are unknowns. It had looked as though fool would simply compose into two half kites back-to-back (sharing their long edge not their join), but the unknowns show there are other possible choices. Each unknown could become a largeKiteCentre or a largeDartBase.
The question is then what to do with unknowns.
Partial Compositions
In fact our composeG resolves two problems when dealing with finite patches. One is the unknowns and the other is critical missing faces needed to make up a new face (e.g the absence of any half dart).
It is implemented using an intermediary function for partial composition
partCompose:: Tgraph -> ([TileFace],Tgraph) partCompose will compose everything that is uniquely determined, but will leave out faces round the boundary which cannot be determined or cannot be included in a new face. It returns the faces of the argument graph that were not used, along with the composed graph.
Figure 9 shows the result of partCompose applied to two graphs. [These are force kiteD3 and force dartD3 on the left. Force is described later]. In each case, the excluded faces of the starting graph are shown in pale green, overlaid by the composed graph on the right.
Then composeG is simply defined to keep the composed faces and ignore the unused faces produced by partCompose.
composeG:: Tgraph -> Tgraph
composeG = snd . partCompose This approach avoids making a decision about unknowns when composing, but it may lose some information by throwing away the uncomposed faces.
For correct Tgraphs g, if decomposeG g has no unknowns, then composeG is a left inverse to decomposeG. However, if we take g to be two kite halves sharing their long edge (not their join edge), then these decompose to fool which produces an empty graph when recomposed. Thus we do not have g = composeG (decomposeG g) in general. On the other hand we do have g = composeG (decomposeG g) for correct whole-tile Tgraphs g (whole-tile means all half-tiles of g have their matching half-tile on their join edge in g)
Later (figure 21) we show another exception to g = composeG(decomposeG g) with an incorrect tiling.
We make use of
selectFacesVP :: [TileFace] -> VPatch -> VPatch
removeFacesVP :: [TileFace] -> VPatch -> VPatch
selectFacesGtoVP :: [TileFace] -> Tgraph -> VPatch
removeFacesGtoVP :: [TileFace] -> Tgraph -> VPatchfor creating VPatches from selected tile faces of a Tgraph or VPatch. This allows us to represent and draw a subgraph which need not be connected nor satisfy the no crossing boundaries property provided the Tgraph it was derived from had these properties.
Forcing
When building up a tiling, following the rules, there is often no choice about what tile can be added alongside certain tile edges at the boundary. Such additions are forced by the existing patch of tiles and the rules. For example, if a half tile has its join edge on the boundary, the unique mirror half tile is the only possibility for adding a face to that edge. Similarly, the short edge of a left (respectively, right) dart can only be matched with the short edge of a right (respectively, left) kite. We also make use of the fact that only 7 types of vertex can appear in (the interior of) a patch, so on a boundary vertex we sometimes have enough of the faces to determine the vertex type. These are given the following names in the literature (shown in figure 10): sun, star, jack (=largeDartBase), queen, king, ace, deuce (=largeKiteCentre).
The function
force :: Tgraph -> Tgraphwill add some faces on the boundary that are forced (i.e new faces where there is exactly one possible choice). For example:
- When a join edge is on the boundary – add the missing half tile to make a whole tile.
- When a half dart has its short edge on the boundary – add the half kite that must be on the short edge.
- When a vertex is both a dart origin and a kite wing (it must be a queen or king vertex) – if there is a boundary short edge of a kite half at the vertex, add another kite half sharing the short edge, (this converts 1 kite to 2 and 3 kites to 4 in combination with the first rule).
- When two half kites share a short edge their common
oppVvertex must be a deuce vertex – add any missing half darts needed to complete the vertex. - …
Figure 11 shows foolDminus (which is foolD with 3 faces removed) on the left and the result of forcing, ie force foolDminus on the right which is the same graph we get from force foolD.
foolDminus =
removeFaces [RD(6,14,11), LD(6,12,14), RK(5,13,2)] foolD
Figures 12, 13 and 14 illustrate the result of forcing a 5-times decomposed kite, a 5-times decomposed dart, and a 5-times decomposed sun (respectively). The first two figures reproduce diagrams from an article by Roger Penrose illustrating the extent of influence of tiles round a decomposed kite and dart. [Penrose R Tilings and quasi-crystals; a non-local growth problem? in Aperiodicity and Order 2, edited by Jarich M, Academic Press, 1989. (fig 14)].
In figure 15, the bottom row shows successive decompositions of a dart (dashed blue arrows from right to left), so applying composeG to each dart will go back (green arrows from left to right). The black vertical arrows are force. The solid blue arrows from right to left are (force . decomposeG) being applied to the successive forced graphs. The green arrows in the reverse direction are composeG again and the intermediate (partCompose) figures are shown in the top row with the ignored faces in pale green.
Figure 16 shows the forced graphs of the seven vertex types (with the starting graphs in red) along with a kite (top right).
These are related to each other as shown in the columns. Each graph composes to the one above (an empty graph for the ones in the top row) and the graph below is its forced decomposition. [The rows have been scaled differently to make the vertex types easier to see.]
Adding Faces to a Tgraph
This is technically tricky because we need to discover what vertices (and implicitly edges) need to be newly created and which ones already exist in the Tgraph. This goes beyond a simple graph operation and requires use of the geometry of the faces. We have chosen not to do a full conversion to vectors to work out all the geometry, but instead we introduce a local representation of angles at a vertex allowing a simple equality test.
Integer Angles
All vertex angles are integer multiples of 1/10th turn (mod 10) so we use these integers for face internal angles and boundary external angles. The face adding process always adds to the right of a given directed edge (a,b) which must be a boundary directed edge. [Adding to the left of an edge (a,b) would mean that (b,a) will be the boundary direction and so we are really adding to the right of (b,a)]. Face adding looks to see if either of the two other edges already exist in the graph by considering the end points a and b to which the new face is to be added, and checking angles.
This allows an edge in a particular sought direction to be discovered. If it is not found it is assumed not to exist. However, this will be undermined, there are crossing boundaries . In this case there must be more than two boundary directed edges at the vertex and there is no unique external angle.
Establishing the no crossing boundaries property ensures these failures cannot occur. We can easily check this property for newly created graphs (with checkedTgraph) and the face adding operations cannot create crossing boundaries.
Touching Vertices and Crossing Boundaries
When a new face to be added on (a,b) has neither of the other two edges already in the graph, the third vertex needs to be created. However it could already exist in the Tgraph – it is not on an edge coming from a or b but from another non-local part of the Tgraph. We call this a touching vertex. If we simply added a new vertex without checking for a clash this would create a nonsense graph. However, if we do check and find an existing vertex, we still cannot add the face using this because it would create a crossing boundary.
Our version of forcing prevents face additions that would create a touching vertex/crossing boundary by calculating the positions of boundary vertices.
No conflicting edges
There is a final (simple) check when adding a new face, to prevent a long edge (phiEdge) sharing with a short edge. This can arise if we force an incorrect graph (as we will see later).
Implementing Forcing
Our order of forcing prioritises updates (face additions) which do not introduce a new vertex. Such safe updates are easy to recognise and they do not require a touching vertex check. Surprisingly, this pretty much removes the problem of touching vertices altogether.
As an illustration, consider foolDMinus again on the left of figure 11. Adding the left dart onto edge (12,14) is not a safe addition (and would create a crossing boundary at 6). However, adding the right dart RD(6,14,11) is safe and creates the new edge (6,14) which then makes the left dart addition safe. In fact it takes some contrivance to come up with a Tgraph with an update that could fail the check during forcing when safe cases are always done first. Figure 17 shows such a contrived Tgraph formed by removing the faces shown in green from a twice decomposed sun on the left. The forced result is shown on the right. When there are no safe cases, we need to try an unsafe one. The four green faces at the bottom are blocked by the touching vertex check. This leaves any one of 9 half-kites at the centre which would pass the check. But after just one of these is added, the check is not needed again. There is always a safe addition to be done at each step until all the green faces are added.
Boundary information
The implementation of forcing has been made more efficient by calculating some boundary information in advance. This boundary information uses a type Boundary
data Boundary
= Boundary
{ bDedges :: [(Vertex,Vertex)]
, bvFacesMap :: Mapping Vertex [TileFace]
, bvLocMap :: Mapping Vertex (Point V2 Double)
, allFaces :: [TileFace]
, allVertices :: [Vertex]
, nextVertex :: Vertex
} deriving (Show)This records the boundary directed edges (bDedges) plus a mapping of the boundary vertices to their incident faces (bvFacesMap) plus a mapping of the boundary vertices to their positions (bvLocMap). It also keeps track of all the faces and vertices. The boundary information is easily incremented for each face addition without being recalculated from scratch, and a final graph with all the new faces is easily recovered from the boundary information when there are no more updates.
makeBoundary :: Tgraph -> Boundary
recoverGraph :: Boundary -> TgraphThe saving that comes from using boundaries lies in efficient incremental changes to boundary information and, of course, in avoiding the need to consider internal faces. As a further optimisation we keep track of updates in a mapping from boundary directed edges to updates, and supply a list of affected edges after an update so the update calculator (update generator) need only revise these. The boundary and mapping are combined in a force state.
type UpdateMap = Mapping DEdge Update
type UpdateGenerator = Boundary -> [DEdge] -> UpdateMap
data ForceState = ForceState
{ boundaryState:: Boundary
, updateMap:: UpdateMap
}
Forcing then involves using a specific update generator (allUGenerator) and initialising the state, then using the recursive forceAll which keeps doing updates until there are no more, before recovering the final graph.
force:: Tgraph -> Tgraph
force = forceWith allUGenerator
forceWith:: UpdateGenerator -> Tgraph -> Tgraph
forceWith uGen = recoverGraph . boundaryState .
forceAll uGen . initForceState uGen
forceAll :: UpdateGenerator -> ForceState -> ForceState
initForceState :: UpdateGenerator -> Tgraph -> ForceState
In addition to force we can easily define
wholeTiles:: Tgraph -> Tgraph
wholeTiles = forceWith wholeTileUpdates which just uses the first forcing rule to make sure every half-tile has a matching other half.
We also have a version of force which counts to a specific number of face additions.
stepForceWith :: UpdateGenerator -> Int -> ForceState -> ForceState
This proved essential in uncovering problems of accumulated innaccuracy in calculating boundary positions (now fixed).
Some Other Experiments
Below we describe results of some experiments using the tools introduced above. Specifically: emplacements, sub-Tgraphs, incorrect tilings, and composition choices.
Emplacements
The finite number of rules used in forcing are based on local boundary vertex and edge information only. We may be able to improve on this by considering a composition and forcing at the next level up before decomposing and forcing again. This thus considers slightly broader local information. In fact we can iterate this process to all the higher levels of composition. Some graphs produce an empty graph when composed so we can regard those as maximal compositions. For example composeG fool produces an empty graph.
The idea now is to take an arbitrary graph and apply (composeG . force) repeatedly to find its maximally composed graph, then to force the maximal graph before applying (force . decomposeG) repeatedly back down to the starting level (so the same number of decompositions as compositions).
We call the function emplace, and call the result the emplacement of the starting graph as it shows a region of influence around the starting graph.
With earlier versions of forcing when we had fewer rules, emplace g often extended force g for a Tgraph g. This allowed the identification of some new rules. Since adding the new rules we have not yet found graphs with different results from force and emplace. [Although, the vertex labelling of the result will usually be different].
Sub-Tgraphs
In figure 18 on the left we have a four times decomposed dart dartD4 followed by two sub-Tgraphs brokenDart and badlyBrokenDart which are constructed by removing faces from dartD4 (but retaining the connectedness condition and the no crossing boundaries condition). These all produce the same forced result (depicted middle row left in figure 15).
However, if we do compositions without forcing first we find badlyBrokenDart fails because it produces a graph with crossing boundaries after 3 compositions. So composeG on its own is not always safe, where safe means guaranteed to produce a valid Tgraph from a valid correct Tgraph.
In other experiments we tried force on Tgraphs with holes and on incomplete boundaries around a potential hole. For example, we have taken the boundary faces of a forced, 5 times decomposed dart, then removed a few more faces to make a gap (which is still a valid Tgraph). This is shown at the top in figure 19. The result of forcing reconstructs the complete original forced graph. The bottom figure shows an intermediate stage after 2200 face additions. The gap cannot be closed off to make a hole as this would create a crossing boundary, but the channel does get filled and eventually closes the gap without creating a hole.
Incorrect Tilings
When we say a Tgraph g is a correct graph (respectively: incorrect graph), we mean g represents a correct tiling (respectively: incorrect tiling). A simple example of an incorrect graph is a kite with a dart on each side (called a mistake by Penrose) shown on the left of figure 20.
*Main> mistake
Tgraph { vertices = [1,2,4,3,5,6,7,8]
, faces = [RK (1,2,4),LK (1,3,2),RD (3,1,5)
,LD (4,6,1),LD (3,5,7),RD (4,8,6)
]
}If we try to force (or emplace) this graph it produces an error in construction which is detected by the test for conflicting edge types (a phiEdge sharing with a non-phiEdge).
*Main> force mistake
Tgraph {vertices = *** Exception: doUpdate:(incorrect tiling)
Conflicting new face RK (11,1,6)
with neighbouring faces
[RK (9,1,11),LK (9,5,1),RK (1,2,4),LK (1,3,2),RD (3,1,5),LD (4,6,1),RD (4,8,6)]
in boundary
Boundary ...In figure 20 on the right, we see that after successfully constructing the two whole kites on the top dart short edges, there is an attempt to add an RK on edge (1,6). The process finds an existing edge (1,11) in the correct direction for one of the new edges so tries to add the erroneous RK (11,1,6) which fails a noConflicts test.
So it is certainly true that incorrect graphs may fail on forcing, but forcing cannot create an incorrect graph from a correct graph.
If we apply decomposeG to mistake it produces another incorrect graph (which is similarly detected if we apply force), but will nevertheless still compose back to mistake if we do not try to force.
Interestingly, though, the incorrectness of a graph is not always preserved by decomposeG. If we start with mistake1 which is mistake with just two of the half darts (and also an incorrect tiling) we still get a similar failure on forcing, but decomposeG mistake1 is no longer incorrect. If we apply composeG to the result or force then composeG the mistake is thrown away to leave just a kite (see figure 21). This is an example where composeG is not a left inverse to either decomposeG or (force . decomposeG).
Composing with Choices
We know that unknowns indicate possible choices (although some choices may lead to incorrect graphs). As an experiment we introduce
makeChoices :: Tgraph -> [Tgraph]which produces 
forceLDB which forces an unknown to be a largeDartBase by adding an appropriate joined half dart at the node, and forceLKC which forces an unknown to be a largeKiteCentre by adding a half dart and a whole kite at the node (making up the 3 pieces for a larger half kite).
Figure 22 illustrates the four choices for composing fool this way. The top row has the four choices of makeChoices fool (with the fool shown embeded in red in each case). The bottom row shows the result of applying composeG to each choice.
In this case, all four compositions are correct tilings. The problem is that, in general, some of the choices may lead to incorrect tilings. More specifically, a choice of one unknown can determine what other unknowns have to become with constraints such as
- a and b have to be opposite choices
- a and b have to be the same choice
- a and b cannot both be largeKiteCentres
- a and b cannot both be largeDartBases
This analysis of constraints on unknowns is not trivial. The potential exponential results from choices suggests we should compose and force as much as possible and only consider unknowns of a maximal graph.
For calculating the emplacement of a graph, we first find the forced maximal graph before decomposing. We could also consider using makeChoices at this top step when there are unknowns, i.e a version of emplace which produces these alternative results (emplaceChoices)
The result of emplaceChoices is illustrated for foolD in figure 23. The first force and composition is unique producing the fool level at which point we get 4 alternatives each of which compose further as previously illustrated in figure 22. Each of these are forced, then decomposed and forced, decomposed and forced again back down to the starting level. In figure 23 foolD is overlaid on the 4 alternative results. What they have in common is (as you might expect) emplace foolD which equals force foolD and is the graph shown on the right of figure 11.
Future Work
I am collaborating with Stephen Huggett who suggested the use of graphs for exploring properties of the tilings. We now have some tools to experiment with but we would also like to complete some formalisation and proofs. For example, we do not know if force g always produces the same result as emplace g. [Update (August 2022): We now have an example where force g strictly includes emplace g].
It would also be good to establish that g is incorrect iff force g fails.
We have other conjectures relating to subgraph ordering of Tgraphs and Galois connections to explore.
which we write as 
and so 
, 
and 
.
but we can rescale at any time.)
is a linear operator (such as the laplace operator 
or higher order or lower order partial derivatives or any linear combination of these), 
is given and 
is the function we want to solve for, and both are defined on a region 
. The multigrid scheme starts with a fine grid 
(where 
is the grid spacing) on which we want to obtain an approximate solution by finite difference methods. The scheme involves the use of a coarser grid (e.g. 
) and, recursively, a stack of coarser and coarser grids to apply error correction on approximations. The full multigrid scheme also uses coarser grids to improve initial approximations used by multigrid.
on the fine grid (
.
are called the residuals (
) and these we can calculate.
,
and get a corrected guess
to get a final approximation.
we want a (linear) mapping that is full rank. E.g identity plus averaging neighbours.
or take some weighting of neighbours as well. A common requirement is that this is also linear and a constant times the transpose of the interpolation when these are expressed as matrix operations.
for some function 
on the boundary 
. We will take the standard approach of representing the boundary conditions using a mask array (with 0’s indicating boundary positions and 1’s at non-boundary positions) along with a boundary values array which has 0’s at non-boundary positions. This will enable us to adapt these two arrays for different coarsenesses of grid.
. We can thus assume two dimensional arrays represent 
, Poisson’s equation has the form
subject to the Dirichlet boundary condition 
for 
, then we divide by 4 and reset the boundary with the mask and values.
, we can use the same formula as above to approximate 
. Rearranging we have 
by 
between 0 and 1. This slightly increases runtime, but does not improve errors for 
, where 
is a scalar potential (such as temperature) over a smooth surface.
in the 
direction and 
in the 
direction). Approximating solutions numerically amounts to approximating a fixedpoint for the grid values satisfying the boundary values and also, for non-boundary points (i,j) satisfying
then this simplifies to
from previous values 
until the iterations are close enough to converging.
for calculated values in the previous column and in the previouus row).
as the weight we calculate first 
(substituting 
readerunner 