Is the spiral effect psychological?

In 2017 [1] a definition of spiral tilings was given, thereby answering a question posed by Grünbaum and Shephard in the late 1970s. The author had the pleasure to discuss the topic via e-mail with Branko Grünbaum in his 87th year. During this correspondence the question arose whether a spiral structure (given a certain definition of it) could be recognized automatically or whether “to some extent, at least, the spiral effect is psychological”, as Grünbaum and Shephard had conjectured in 1987 (see exercise section of chapter 9.5 in [4]). In this paper, an algorithm for automatic detection of such a tiling’s spiral structure and its first implementation results will be discussed. Finally, the definitions for several types of spiral tilings will be refined based on this investigation.

Figure 1

Spiral structure “by coloring” (left) vs. “by construction” (right)

If in Figure 1 all colors of tiles were erased and only the tile structure remained, in the left tiling (of simple squares) nobody could find a spiral character. On the other hand, the right tiling contains the spiral structure by construction, although not so easily recognized without coloring.

One key aspect of the definition of spiral tilings in [1] is that it gives a basis to distinguish between tilings in which the spirals were just introduced by coloring and those which incorporate a spiral structure. The two tilings of Figure 1 represent both types of spirals. For the latter type we will define a further distinction at the end of this paper.

During this study, we assume that all tiles are closed topological disks. If not specified explicitly, we assume that no singular points exist, where the tiles are clustered. All investigated tilings without such singular points are assumed to be $k$-hedral, which means that there are only finitely many congruence classes. We will refer to the definitions from [1] throughout this paper, so, we decided to put them into the appendix to have them at hand. First we need the term L-tiling which can be summarized using ordinary language:

“An L-tiling allows a partitioning into several parts (called arms), in each of which we can draw a continuous, unlimited curve (called thread) running through the interior of each tile (of the part) exactly once and winding infinitely often around a certain point”. In the appendix the reader may have a look for this definition in strict mathematical terms, but for the further understanding this one-sentence-version should be sufficient. (The left hand part of Figure 1 serves as an example of an L-tiling.)

Also the term S-tiling from [1] can be summarized in ordinary words: “An S-tiling must have the properties of an L-tiling plus an extra property that neighboring tiles within each arm are positioned to each other in a way that cannot occur with two neighbored tiles from different arms (except at the beginning of an arm)”. E.g., a closer inspection of Figure 1 (right) shows that within each arm (equal color) there are just two different constellations of neighboring tiles, and both constellations do not occur with tiles of different colors. So, this is an S-tiling. (See again the appendix for a more rigid definition.)

Then for our algorithm we need another pair of definitions.

Definition

direct contact graph (DG) and contact graph (CG):

Let $M$ be a connected set of some tiles of a tiling. Then the “contact graph of$M$” or CG(M) is the graph in which each tile of $M$ is represented by a node and two of such nodes are connected by an edge iff the corresponding tiles “have contact”, i.e., have non-empty intersection [5]. We can construct a subgraph of CG(M) called “direct contact graph of $M$” or DG(M) by deleting all edges for each pair of tiles which share only a finite number of points of their boundaries. (In graph theory this would be called dual graph where the tiling is interpreted as a planar graph.)

Figure 2 shows a simple example of DG and CG for a small subset of the square tiling. Observe that CG in many cases will not be planar. Both DG and CG can be finite or infinite, depending on the choice of M.

Looking at the above-mentioned definitions for S-tilings, we observe that they start with a partitioning of the tiling, but do not tell us how to find it (in our example in Figure 1 “partition” and “coloring” are equivalent). So, if any automatic recognition is possible, it must deliver a partitioning into “spiral arms”. Given these partitions (or arms in terms of our definition) it is clear how to proceed further: Check whether a continuous curve (a so-called thread) can be found satisfying the necessary conditions. For practical reasons, we decided to search for Hamilton paths [3] within each candidate for a spiral arm. Although this is not equivalent to definition L or S, for a huge subset of S-tilings (maybe for all of them) the spiral arms can be regarded as Hamiltonian w.r.t DG or CG. This can be easily implemented using graph libraries. (A Hamilton path within a connected component of DG or CG means that we can walk through the component along its edges meeting every node exactly once.)

Let us first describe the main ideas of the algorithm just by words:

• •

  Build classes of neighboring tile pairs according to their relative position to each other

• •

  For each possible subset of these classes cut the tiling at the intersection of each tile pair belonging to one of the selected classes

• •

  After each cut check the resulting connected components whether they allow a Hamilton path running through each component of the (direct) contact graph winding around a central point

To give an example, in Figure 2.1 we can find four classes of tile pairs (one connected by a short edge and three others sharing a long edge in different ways).

Figure 2.1

Example: spiral tiling (left) and result from the algorithm (right)

It is obvious that just the connections via “short” edges had to be deleted by the algorithm to find the spiral structure. In this case it is a two-arm spiral where both arms meet at the center. We see (at the right half of Figure 2.1) the direct contact graph (DG) of the tiling after the described cut.

Now the more formal description must follow: For an algorithmic approach, we have to restrict our scope to finite portions of a given tiling. Throughout this section let $M$ be the investigated portion of a tiling that should be checked by our algorithm. In section 4 the appropriate choice of M will be addressed. Those tiles in $M$ which are (in the unlimited tiling) neighbors of tiles lying outside of $M$ are called the border $B_{M}$. Then CG(M) (or CG for short) is the contact graph of M and DG(M) (or DG) the corresponding direct contact graph. We start with classifying all edges in these graphs depending on how their corresponding tile pairs in $M$ are positioned to each other:

For each edge $k$ of $DG$ we form the class [$k$] consisting of all the edges $k^{\prime}$ of $DG$ for which the two tiles (determined by the endpoints of $k^{\prime}$) are congruent to the corresponding tiles determined by $k$, through an orientation-preserving isometry of the plane (that is, by translation or rotation). Let the set of all such classes be denoted $K_{M}=\left\{[k_{1}],[k_{2}],\text{\ldots}\right\}$.¹¹1One could call such classes edge classes or tile pair classes, which is equivalent here. (During the algorithm we will also need additional edge classes from $CG$, constructed in the same way.) For a class [$k$] we consider the set $E(k)$ of edges in [$k$]. For each subset of classes K $\subset K_{M}$ we write E(K) for the corresponding edge set as a union of $E(k)$. An edge from E(K) between the tiles $T_{1}$ and $T_{2}$ should be denoted as $(T_{1},T_{2})$. For each of these subsets of edge classes in $DG$ we can check what happens if all these edges were deleted. How do the remaining connected components of $DG$ “behave”? Several steps were included in order to exit the loops as early as possible.

For shortness, we will use the term “component” for “connected component”.

Algorithm:

First check whether there are at least three congruent tiles differing in orientation or reflection within $M$.
If not, end the algorithm with empty result.
Else, form the set of classes $K_{M}$ as described above.
Next we define an operation to be performed on each nonempty K$\subset$ $K_{M}$.

Operation A:

(using K as input and returning either K plus a graph or the result “discarded” if K cannot fulfill a condition)

Check whether all components of $\bigcup\limits_{(T_{i},T_{j})\in E(\boldsymbol{K})}\!\!\!\!\!\!\!\!\!T_{i}\cap T_{j}\,\,\,$ are connected to the border $B_{M}$; [Remark: Represents boundaries of spiral arms.]

if not, discard K and finish Operation A with result “discarded”;

if yes, delete the edges E(K) from $DG$, the result is called $G$;

if all components of $G$ are connected to $B_{M}$ and allow a Hamilton path without self-intersections, go directly to (*);

else, do the following steps with K plus any combination of edge classes from $CG$, called “K-extension”, each of which generates a new $G$:

If for such an extended K a component of the new $G$ is not connected to $B_{M}$ or does not allow a self-avoiding Hamilton path, ignore this K-extension and try the next possible one;

if a tile in $M$ has more than two vertices where it meets other tiles at single points (being connected to these tiles by edges in the new $G$), ignore this K-extension and try the next possible one; [Remark: Excluding cases like the checkers tiling in [1] Figure 3, where a spiral arm is not simply connected.]

(*)

If for each component of $G$ the number of tile equivalence classes w.r.t translation is less than 3 – discard (extended) K and continue with the next one (if extensions were needed);

if extensions were needed, return all non-discarded variants of K plus $G$ or “discarded” as result when all extensions were checked;

else return (K, $G$) if non-discarded or else return “discarded”.

(End of A)

Perform Operation A with all nonempty subsets of $K_{M}$. All non-discarded subsets are candidates for spiral partitions. Sort the non-discarded subsets by the number of components of $G$ (= nbr. of arms) in increasing order.

Operation B:

(using each non-discarded $G$ as input if there is any)

For each component of $G$: Find a continuous piece-wise linear curve through the corresponding tiles following the possible Hamilton paths and modify it to check whether the conditions for being a thread can be fulfilled. [Remark: this section of the algorithm is not difficult for the human eye but needs considerable programming efforts. On the other hand, by methods of computer graphics and optimization this task could be handled in principle. Since the above-mentioned “psychological effect” is not needed here, we decided not to code this section of the algorithm.]

If one component does not allow a thread, $G$ has to be discarded. As a final result the components of $G$ each with a valid thread represent the spiral arms.

End of Algorithm

This algorithm (except for Operation B) was implemented in Python, which is by far not the fastest language but offers a lot of libraries for graph operations.

Let us return to the example in Figure 2.1. The separation into two arms cannot be managed by the implemented algorithm, but the spiral structure was recognized. Only the direct contact graph is needed in this case, but there will be some examples with CG in the following section.

As a set of test cases we took several tilings from [2] with spiral structure.

It is interesting to note that the algorithm also works for one-armed spirals. Though the definition for this type differs slightly from Definition S (see Appendix: Definition O for more details) the algorithm (up to Operation B) can be applied without any changes. Operation B can be performed here in simplified version, since only the spiral boundary curve has to be checked if it is winding around its starting point. In the above-mentioned collection of spiral tilings [2] there are two examples for this case (Figure 3.3).

Figure 3.4

Two different S-partitions for the same tiling

The spiral arms on the right side of Figure 3.4 do not look very “natural” compared to the spirals on the left half, but they fulfill all conditions for an S-tiling. Only the heuristic argument could be applied that the partition with lower number of arms should be preferred. This is the reason for the final part of the algorithm, where a sorting of the resulting graphs has been proposed to find the result with lowest number of connected components.

It is quite obvious that an algorithm containing a loop over all subsets of a given finite set must have exponential complexity (w.r.t. the number of edge classes $|K_{M}|$). Hence, there will be cases where the algorithm’s runtime outruns all practical limits. It should be noted here that the whole investigation did not aim on efficient implementation, but to answer the question whether such an algorithm exists at all.

What can be done now in cases of extremely long runtime? Such examples exist, but we are lucky that they are rare. For these few cases we propose to apply an algorithmic test “by hand” in a way that the following items should be checked to decide whether the algorithm will (or won’t) be successful. We use again the simple structure of Figure 2.1 to illustrate the steps:

• •

  classify all edges of the direct contact graph DG by assigning integers for each class of direct neighbors to define the edge classes $K_{M}$ (In Figure 2.1 there are four classes: Let us assign 1 to the neighbors sharing a short edge and 2, 3 and 4 to the other classes of neighbors sharing a long edge.)

• •

  if spiral arms can be observed by the human eye: Consider the spiral arms as subsets of $M$ and run along their boundaries to find the specific subset K of $K_{M}$. If a spiral arm locally shrinks to a single point, as in Figure 1 (right), go back to the previous item but use CG (In our example in Figure 2.1 just DG is needed and the arms’ boundaries are easily characterized just by the short edges, so we choose K = {1}.)

• •

  check whether the chosen K finishes Operation A without being discarded (This is easily checked in our example since the tiling contains more than three tiles with different rotation angles and each component of the resulting $G$ - after deleting the connections via short edges - can be naturally traversed by a Hamilton path. All these paths are connected to the outside border region, which is also true for the arms’ boundary.)

• •

  perform Operation B for the components of the non-discarded results of Operation A, i.e., find a thread - or maybe several of them - following the Hamilton path(s) (In our example this is done straight forward with two threads starting close to the tiling’s center.)

If by these checks a single subset K is found not being discarded by Operation A, it is shown that the algorithm must find this result within finite time. All remaining tilings from the literature (less than 10) were investigated with the result that in all cases where definition S is satisfied, the algorithm will return a spiral partition. Also the somehow unexpected spiral structure within the Hirschhorn tiling can be detected by this analysis (discussed in the last section, see Figure 5.2). In the same section we will see another simple example which demonstrates the advantages of the algorithm’s application “by hand”.

There is one interesting case in Brian Wichman’s collection [2] showing kind of disrupted spiral arms (see Figure 4.1). The two arms indicated by two different colors are following a spiral structure from inside to outside, but it is not possible to draw a continuous path following the spiral within the interior of each arm.

Figure 4.1

A tiling from [2] with disrupted spiral arms

Our algorithm (here not by hand but by software) returned a negative result in this case, which is correct since neither definition S nor even L can be satisfied.

By its nature, an algorithm working on a finite portion of the tiling cannot in all cases distinguish between “true” spirals and partitions which start like spirals but later stop the spiral behavior. (Figure 11 in [1] shows an example of such a pseudo-spiral partition.) Therefore one could start the algorithm with a smaller part of the tiling as described and then add further tiles outside of the so-called border region. Then one could check whether the orientation of the tiles within a spiral arm will further change or remains in one or two fixed angular positions. In addition, a further difficulty could occur: It is not sure that the spiral center is always placed in the middle of the finite portion of the tiling. So, one might first look for this center by searching for the part where the highest number of tiles with different orientation are clustered.

The proposed refinements from this section are all possible in principle but the described version of the algorithm worked well enough without it.

The main result of this paper is the fact that an algorithm can be designed to decide whether a given tiling has or doesn’t have a spiral structure. This is done by a method of partitioning into spiral arms. As we have seen in the results section, the proposed algorithm can be applied to a wide range of tilings. We can claim that all known spiral tilings from the literature (in the meaning of definition S or O resp.) can be detected by the algorithm. The vast majority was covered by our Python implementation while the remaining part (less than 10) could be analyzed “by hand” following the algorithmic check list described in the previous section. So, the algorithm is working as desired with the limitation of not being very efficient for all cases due to its exponential complexity.

This application “by hand” can also be used to decide whether a given tiling contains more than one spiral structure.

We can demonstrate this with a tiling presented in [1] to find out whether more than one spiral arm exists in this case (see Figure 5.1). First, we cut the tiling at those edges shared by two tringles (= thick line) to get the left hand version (one spiral arm). Alternatively - on the right hand side - we cut the same tiling at those edges where a triangle meets a rhombus (= edges shared between dark grey and light grey tiles) to find the right hand partitioning (two spiral arms). This means that the algorithm “by hand” can also be used as a method to partition a given tiling for a better understanding of its structure.

The concept of structure analysis developed in this paper can be used for other structures than spirals, as well. In any case the final result is a tile set partition, where in each part the tiles are positioned to each other in a different way than on the parts’ boundaries. So, one could ask, what typical structures could be found in this way: For the large domain of periodic tilings, we will often find partitions in form of stripes or patches. For non-periodic tilings, especially with rotational symmetry - but not restricted to those - we will detect ring-like structures, where each ring is surrounded by a larger one. For such ring partitions, we distinguish two types which can be defined in a way analogous to definition L and S.

Definition

weak ring partition: A tile set partition of a plane tiling into infinitely many parts is called a weak ring partition if each part (as union of its tiles) contains a closed Jordan curve $\theta$ (called thread) around a fixed central point, $\theta(t)=r(t)\exp{(i\varphi(t))}$ with the plane identified with $\mathbb{C}$, $r(t)>0$, $t\in[0,1]$ and $\varphi$ being monotonic with $\varphi([0,1])=[0,2\pi]$. For each tile $T$ in the part the intersection of the interior of $T$ with the image of $\theta$ is nonempty and connected. The threads do not meet or cross each other.

Note that this definition could also be used for tilings with a singular point, where arbitrarily small tiles are clusterd. Apart from this, a huge number of tilings allow weak ring partitions, however, it is not a simple question how to characterize the family of tilings that share this property. We can pose this as an open problem so far.

For the further analysis we need a stronger version of this definition. The condition is analogous to S2 from definition S with ‘arm’ replaced by ‘part’:

Definition

strong ring partition: A tile set partition of a plane tiling with all properties of a weak ring partition is called a strong ring partition if an additional condition holds: If any two tiles $T_{1},T_{2}$ in a part are direct neighbors and can be respectively mapped by an operation $\tau$ (composed of translation, rotation or scaling) onto another tile pair $\tau(T_{1})$ and $\tau(T_{2})$, these must also be direct neighbors within a part. ($T_{1},T_{2}$ from the same part are called direct neighbors if $T_{1}\text{$\cap$}T_{2}$ is cut²²2Here and in all other occurrences ”cut by the thread” means that the thread (by passing from $T_{1}$ to $T_{2}$) intersects $T_{1}\text{$\cap$}T_{2}$, which might also be just a single vertex. by the part’s thread or contains more than a finite number of points.)

Figure 5.2 (left) shows an example of a strong ring partition. The scaling operation was inserted here to make this definition applicable also in the context of tilings with singular points, see below in this section. It is obvious that by the techniques of the algorithm presented in section 2 one could automatically check whether a tiling allows or doesn’t allow a strong ring partition.

Now we can separate tilings with a spiral structure from those with a ring structure, which sometimes can both occur simultaneously.

Definition:

A $k$-hedral tiling is called a strong spiral tiling (respectively strong S-tiling or strong O-tiling) if it is an S- or O-tiling and additionally doesn’t allow a strong ring partition. (Hence, strong spiral tilings and strong ring partitions exclude each other.)

A closer inspection shows that most of the known S- or O-tilings are also strong S- respectively strong O-tilings. A famous example where this is not the case is the Hirschhorn tiling. In Figure 5.2 we can observe on the left side the obvious ring structure and on the right side the spiral arms allowing an S-partition.

In the context of tilings with one singular point, we can do the same to separate the ring structure from the spirals.

Definition:

A tiling with one singular point and finitely many similarity classes is called a strong spiral tiling (or strong P-tiling) if it allows a partition according to definition P but doesn’t allow a strong ring partition.

Tilings with strong ring partition and spiral structure - regardless of having a singular point or not - as shown in Figure 5.2 or in [6] often have the property that the spirals are in some sense hidden or visually dominated by the ring structure. They can be viewed as “picture puzzles”. So, though we have demonstrated that spirals (and other structures) can be detected principally without human aid by algorithms, in the context of perception the quote from the beginning remains true that “to some extent, at least, the spiral effect is psychological”.

Although it is no longer possible in person, I would like to express my gratitude to the late Branko Grünbaum for the fruitful discussion during the development of this paper and thanks to Brian A. Wichmann for his support with the tilings from his great collection.

Here are the definitions from [1] which are used in this paper. In section 2 we tried to paraphrase them using ordinary language.

Definition L

(spiral-like) :

A partition of a plane tiling into more than one separate classes (called arms here) is defined as a spiral-like partition or L-partition under the following conditions. (The plane is identified with the complex plane $\mathbb{C}$ where the origin is represented by a selected point of the tiling.)

L1:

For each arm $A$ (as a union of tiles from one class) there exists a curve $\theta:\mathbb{R}_{0}^{+}\rightarrow A\text{\,}$$\subset\mathbb{C}$ with $\theta(t)=r(t)\exp{(i\varphi(t))}$ called a thread , where both $r$ and $\varphi$ are continuous and unbounded and $\varphi$ is monotone. Curve $\theta$ does not meet or cross itself or any thread from another arm of the tiling.

L2:

For each tile $T$ in $A$ the intersection of the interior of $T$ with the image of $\theta$ is nonempty and connected.

Remark:

A plane tiling with an L-partition shall be called an L-tiling or a spiral-like tiling.

Definition S:

(for tilings with more than one spiral arm)

A partition of a plane tiling is defined as a spiral partition or S-partition under the following conditions.

S1:

It must be an L-partition (see definition L).

S2:

If any two tiles $T_{1},T_{2}\text{$\in$}A$ are direct neighbors and can be respectively mapped by a direct isometry $\tau$ onto another pair of tiles $\tau(T_{1})$ and $\tau(T_{2})$, these must also be direct neighbors within an arm. This rule can be ignored if the image pair contains the beginning of an arm, i.e., contains $\theta(0)$. ($T_{1},T_{2}\in A$ are called direct neighbors if $T_{1}\text{$\cap$}T_{2}$ is cut by the thread of $A$ or contains more than a finite number of points.)

Remark:

A plane tiling which allows an S-partition shall be called an S-tiling.

Definition O

(for one-armed spirals) :

A tiling of the plane is called a spiral tiling with one arm or an O-tiling under the following conditions (The plane is identified with the complex plane $\mathbb{C}$ where the origin is represented by a selected point of the tiling.)

O1:

There exists a curve $b:\mathbb{R}_{0}^{+}\rightarrow\mathbb{C}$ with $b(t)=r(t)\exp{(i\varphi(t))}$ called spiral boundary, where both $r$ and $\varphi$ are continuous and unbounded. Curve $b$ does not meet or cross itself and runs completely on boundaries of tiles

O2:

If $T_{1},T_{2}$ are direct neighbors and can be respectively mapped by a direct isometry $\tau$ onto another pair of tiles $\tau(T_{1})$ and $\tau(T_{2})$, these tiles must also be direct neighbors. This rule can be ignored if the image pair lies at the beginning of the boundary (i.e., contains $b(0)$). (‘Direct neighbors’ means here that $T_{1}\cap T_{2}$ contains more than a finite number of points but not from the spiral boundary.)

• Definition  P

  (for tilings with one singular point) : A tiling of the Euclidean plane with exactly one singular point together with a partition is called a spiral P-tiling under the following conditions. (The plane is identified with $\mathbb{C}$ where the origin is represented by the singular point.)

• P1:

  The partition fulfills L1 and L2 but with $\theta:\mathbb{R}\rightarrow A\text{\,}\subset\mathbb{C}$ and with $\varphi$ being unbounded in both directions.

• P2:

  If any two tiles $T_{1},T_{2}\text{$\in$}A$ are direct neighbors and can be respectively mapped by an operation $\tau$ (composed of translation, rotation or scaling) onto another pair of tiles $\tau(T_{1})$ and $\tau(T_{2})$, these tiles must also be direct neighbors within an arm. (‘Direct neighbors’ means here that $T_{1}\text{$\cap$}T_{2}$ is cut by the thread of $A$.)