User:Tropylium/Exterior

An exterior of a pattern or a pattern component is a rookwise connected cycle of vacuum cells that encloses the pattern or component in its entirety.

A pattern may have multiple definable minimum exteriors, of which the box exterior (the minimum exterior of the bounding box) is always the largest in area. The "depth" of possible exteriors can measure the concaveness of a pattern.

An exterior can be, while keeping its size constant, shrunken down first to containing the unique bounding octagon of the pattern, further into a "polygon exterior", and from there into a "shrinkwrap exterior" (name suggested by andrewthebonfire on Discord) (both presumably unique). These three variants can be all derived from the box exterior by repeated applications of a corner contraction rule, here in its northeast orientation:

++   +.
,+ → ++

where the dead cell marked by a comma is enclosed by the interior, the dead cell marked by a period is not.

The number of serial (not parallel) contraction steps required to derive the shrinkwrap exterior from the polygon exterior can be called the pattern's degree of slight concavity.

Defining the exterior of a pattern remains difficult in edge cases (sic!), but at minimum can be certainly identified as the shrinkwrap exterior, whenever a pattern is at most n-slightly concave for some n.

The following illustrates the box exterior and the octagon exterior of a 20-cell pattern, both as sets of cells (marked by +) and as cycles:

++++++++++++  ┌──────────┐    +++++++++...  ┌───────┐...
+oo........+  │oo........│    +oo.....++..  │oo.....└┐..
+o.o.o.....+  │o.o.o.....│    +o.o.o...++.  │o.o.o...└┐.
+o....oo...+  │o....oo...│    +o....oo..++  │o....oo..└┐
+o......ooo+  │o......ooo│    +o......ooo+  │o......ooo│
+.oo....o..+  │.oo....o..│    ++oo....o.++  └┐oo....o.┌┘
+...ooooo..+  │...ooooo..│    .++.ooooo++.  .└┐.ooooo┌┘.
++++++++++++  └──────────┘    ..++++++++..  ..└──────┘..

The following are its polygon exterior (with a (3,1) upper right slope and a partly (2,1) lower left slope) and shrinkwrap exterior.

++++........  ┌──┐........    ++++........  ┌──┐........
+oo++++.....  │oo└──┐.....    +oo++++.....  │oo└──┐.....
+o.o.o++++..  │o.o.o└──┐..    +o.o.o+++...  │o.o.o└─┐...
+o....oo.+++  │o....oo.└─┐    +o....oo++++  │o....oo└──┐
+o......ooo+  │o......ooo│    +o......ooo+  │o......ooo│
++oo....o.++  └┐oo....o.┌┘    ++oo....o+++  └┐oo....o┌─┘
.+++ooooo++.  .└─┐ooooo┌┘.    .+++ooooo+..  .└─┐ooooo│..
...+++++++..  ...└─────┘..    ...+++++++..  ...└─────┘..

Deeper concavities in a pattern differ in that they result a larger exterior by cell count (while still decreasing its area). The following pattern is 2-deeply concave; shown with its box exterior (which is also its octagon, polygon and shrinkwrap exterior) as well as example 1-deep and 2-deep exteriors (neither is unique).

++++++++    +++.++++    +++..+++
+o....o+    +o+++.o+    +o+..+o+
+o....o+    +o....o+    +o++++o+
+oooooo+    +oooooo+    +oooooo+
++++++++    ++++++++    ++++++++

To maintain the exterior as a cycle, one-cell indents should not be admitted into it. Two-cell indents seem like a debatable case, where they can allow a cycle, but also allow a smaller cycle within the same set of cells. Here is a putative exterior of a table, in which we can trace either a rookwise cycle comprising all the cells, or also a rookwise cycle that only encompasses the bounding box cells.

++++++   ┌─┐┌─┐   ┌────┐
+o++o+   │o└┘o│   │o++o│
+oooo+   │oooo│   │oooo│
++++++   └────┘   └────┘

3-cell and larger indents do not possess this problem. They can be derived by the following exterior contraction rule:

+++   +.+
,,, → +++

Patterns that are both 0-slightly-concave and 0-concave may be called simply convex.

Properties of exteriors

Distinct minimal exteriors, according to any specific definition, exist for every polyplet / connected component within a pattern that is not itself enclosed by another one.

Whether a component is enclosed depends on which indents are allowed. E.g. in the following pattern, the block is enclosed if 2-wide indents are disallowed, and is not if they are allowed:

..........
..oo..oo..
.oo....oo.
.o......o.
.o..oo..o.
.o..oo..o.
.o......o. 
.oo....oo.
..oooooo..
..........

Two components within a pattern are strictly isolated (or perhaps separated, following topological terminology?) if they have exteriors that are disjoint and neither contains the other. In the context of Life and similar CA, which lack the transitions B1, B2n, B2k and B2i, also two components that share 1 exterior cell or, under some conditions, 2 or 3 consecutive exterior cells (such as two tubs separated by one cell), are usually considered separate in a weaker sense, which we may call isolated.

Stable patterns will not interact as long as they are isolated. However, considering also sparks and other dynamic patterns, it is possible for three components that are all pairwise isolated to still interact. Here a dot spark is 3-isolated from a duoplet spark and 1-isolated from a preblock; yet the cell marked with an asterisk will be born:

.......
..o....
...*...
..o.oo.
.o...o.
.......