Sequence A181785, Wechsler's Convex-Hull Polyominoes

Contents

Introduction

Definition

Convex-Hull Examples

Enumerating the Convex-Hull Polyominoes

Orders 6 through 8

The Inductive Algorithm

Growth Trends

The Disk Polyominoes

Introduction

A Polyomino is a shape made from one or more squares joined together at their edges. This sequence counts a subset of polyominoes that are "convex-like", in a way related to the convex hull of the centers of the squares.

This problem was proposed to the math-fun mailing list on May 5^th 2011 by Allan Wechsler:

On a previous occasion, I talked about enumerating "disklike" polyominoes, polyominoes which occurred as the intersection between a disk and a square lattice. Today I tried counting polyominoes which occurred as the intersection between any convex figure and the lattice. This implies that the convex hull of the polyomino (viewed as a set of lattice points) includes no additional lattice points.

I call these polyominoes "convex", but apparently the term has already been taken by a different class, so I don't know what we should really call them.

Starting from the monomino, the counts seem to be 1, 1, 2, 5, 10, 25. The sequence is not in OEIS, though I confess some uncertainty about the 25 convex hexominoes, and would like confirmation.

The sequence, Sloane's A181785, begins:

1, 1, 2, 5, 10, 25, 48, 107, 193, 365, 621, 1082, 1715, 2777, 4247, 6519, ...

Definition

Given a polyomino P on a square lattice, if you replace each of the squares in P with a point (e.g. its top-left corner) and call that set of points S, then define H to be the convex hull of S :
The polyomino is said to be a convex-hull polyomino if and only if all lattice points in H are also in S.

Polyominoes have an order which is simply the number of squares. There is a unique name for each of the lower orders: monomono, domino, tromino, tetromino, and so on. I also use the number N to refer to the order.

For N=1 through 4 the number of convex-hull polyominoes is the same as the number of polyominoes in general:

o o o o o o o o 1 monomino 1 domino o 2 triominoes o o o o o o o o o o o o o o o o o o o o 5 tetrominoes

Here are the 10 pentominoes that fit the definition:

o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 10 convex-hull pentominoes

There are two pentominoes that do not qualify:

o . o o o o o o . o o o the "U" pentomino the "V" pentomino

As per the definition, imagine replacing each square (or "o" in the figure) with a lattice point. There are 5 lattice points. Then you look at the convex hull of those points. Since we're in 2 dimensions, the convex hull is a solid 2-dimensional region bounded by a polygon. For the U pentomino the bounding polygon is a rectangle; for the V pentomino it is a right isosceles triangle. In both cases there is one additional point, shown here by a dot ".", that lies on that bounding polygon. The "U" and "V" pentominoes fail to be "convex-hull pentominoes" by our definition because the square corresponding to this 6^th lattice point is not part of the pentomino.

Convex-Hull Examples

Here are a few illustrations of how lattice points fall inside or outside a convex hull, and in some cases right on the boundary.

The simplest cases occur when a polyomino has a row or column of square cells, and one square in the next row or column. The most obvious examples are the "L"-shaped tetromino and pentomino. Here the centers of the squares are shown as "*", some neighboring lattice points with dots ".", and the boundary of the convex hull is crudely shown with lines:

*---* *---* | / | / o o * / . o o * . o |/ o | / o * . o * . o |/ The "L" tetromino * . The "L" pentomino

In these cases the nearby lattice points all fall clearly outside the convex hull. The same is true for all similar shapes no matter how long the "L" shape.

The simple "L" diagonal is often seen in two or more parts of a polyomino:

. * . / \ *---*---* o . / * * o o o \ / o o / / o . \ * / . o o * * . o \ / o \ / . * . o . \ * . \ / the "T" pentomino . * . A heptomino

This type of polyomino has a single "spine" (vertical in the figure) with an extra square on each side. Up to four diagonal edges are formed, each with the simple "L" shape illustrated above. No extra lattice points need to be added.

The "V" pentomino was already illustrated above; here we show it, along with the hexomino that results when you add the 6^th square to make it a valid convex-hull polyomino:

*---*---* *---*---* o o o | / o o o | / o * . . o o * * . o | / o | / NO * . . YES * . .

The diagonal edge is at an angle of 45 degrees, and goes right through a lattice point. The square corresponding to that lattice point must be included for it to be a convex-hull polyomino.

The next-simplest case is a diagonal line at a 3-to-2 angle, illustrated here by adding one more square to the previous example:

*---*---* | / o o o * * / . o o | / o * /a . o |/ * . .

The slope of the long diagonal line is 3/2: it goes three units up and two units to the right. It does not reach the lattice point "a", you would need a 45-degree line to do that.

However, if you add one more square on the bottom of the long edge, then the diagonal does touch lattice point "a", and you then need to add another square to make a convex-hull polyomino:

*---*---* | / * * / . o o o o o o | / o o o o * * . o o o | / o o * / . . o o |/ NO YES * . .

These examples in various combinations cover all of the convex-hull patterns up through order 8.

Enumerating the Convex-Hull Polyominoes

Most of the terms of sequence A181785 were automatically computed, as were the illustrations below.

I began with a program that computes the sequence A000105, counting all polyominoes without a convex restriction and with the normal rules about rotations and reflections. This program represents each polyomino as a set of binary digits (0 and 1 "bits") in an array (a grid of rows and columns).

Each polyomino is then tested to see if its convex hull includes any other points. The algorithm is much simpler than other convex hull algorithms because all the points are arranged in rows and columns.

Row Gap Test

The first, and simpler part of this test just looks at each row to see if there are any gaps:

o o o o o o o o o o o o o o o o o o o o NO NO NO

Each of these examples has a row with a gap, and it is pretty easy to see that the lattice point(s) in the gap will either be on the convex hull or will fall within it. Notice in the first two cases the test would fail to catch the gap if the pattern were rotated 90 degrees.

Simply rotating the pattern and doing the gap test again will catch a lot more, but that is not sufficient, as illustrated by the "V" pentomino above.

Testing the Direction of an Angle

The second, and more elaborate, part of the test involves following the left and right ends of the rows and checking for left and right turns. This algorithm needs a way to measure and angle to see if it bends right or left (or straight). I used the following formula, which is used in other convex hull algorithms :

det function from Graham scan. This function computes the determinant of a matrix for a triangle, which tells us the "signed area" of the triangle. The result will be negative or positive depending on whether the three vertices are given in clockwise or counterclockwise order (respectively), or zero if the points are all on a line.

function triangle_signed_area(ax, ay, bx, by, cx, cy)
return [ (bx-ax)(cy-ay) - (by-ay)(cx-ax) ] / 2
end function

This function can be used to determine if an angle bends to the right or the left (or does not bend at all). There is no risk of roundoff error because all lattice points have integer coordinates, and the formula always generates an exact multiple of 1/2. (Since we only care about the sign, in practice the division by 2 need not be performed.) Here is an example, using three points A B and C whose coordinates (x,y) are shown:

(1,2) (2,2) B---C / . / . /. A (0,0)

The formula gives the area of the triangle ABC:

[ (bx-ax)(cy-ay) - (by-ay)(cx-ax) ] / 2
= [ (1-0)×(2-0) - (2-0)×(2-0) ] / 2
= [ 2 - 4 ] / 2 = -1

The answer is negative because the vertices of the triangle (A,B,C) have been given in clockwise order. Saying that these vertices are in clockwise order around the triangle is equivalent to saying that, when going from A to C via B, the angle at B is a "right turn". More tersely, I say "angle ABC is a right turn", or equivalently "angle CBA is a left turn".

If the edges AB and BC are part of a larger polygon, this formula can be used to determine if the angle is concave or convex (according to which side is the "inside").

Left and Right Boundaries

The second, and more elaborate, part of the test involves looking at the rightmost and leftmost ends of the rows. The left ends of the rows are connected with lines to form a "left boundary", and then points are removed as needed to make sure the boundary is convex, using the angle test on sets of neighboring boundary points.

Once the left and right edges of the polyomino are converted into convex boundaries, the program then tests to see if lattice points next to the polyomino fall on or within the boundary. This test can be performed with the same determinant formula, with the test point as point B and using nearby boundary points from rows above and below as the points A and C. Note that the first and last rows of the polyomino do not need to be tested in this way, because the boundary is obviously convex there. Therefore there is always a point A and C available to do this test.

A Complete Example

Here is a walkthrough of a specific example:

. A B . . *---* o o / | o c D e . / * . o o o / | . F G H . *---*---* polyomino lattice points convex hull

The polyomino to be tested is shown in the left part of the figure. The center figure shows the naming of lattice points used in this discussion, and the right figure illustrates the convex hull. To test this polyomino:

First it checks that there are no gaps in any of the rows; this test passes.

Then it looks at the left boundary. Initially it uses all three left endpoints: F, D, A. It checks the angle FDA and sees that this angle bends to the left, so point D is a concave point. Therefore D is interior to the convex hull and is removed from the left boundary. The left boundary then consists of the single edge FA.

To compute the right boundary, it starts with all three points: B, D, H. Once again, the angle BDH is checked and found to be a left turn, and point D is removed from the right boundary. The right boundary then consists of the single edge BH.

(In taller patterns there would be more lattice points to check along both boundaries. Each time a point is removed, the rest are checked again to make sure none of them has been affected.)

The complete convex hull for the polyomino is shown in the right part of the figure; it consists of the top and bottom rows together with the left and right boundaries. This is a trapezoid with vertices at A, B, H and F. Point G is not used at all; in general the top and bottom edge each have at most two vertices.

Next the neighboring lattice points are checked. The lattice points to the left of A and to the right of B (both marked ".") need not be checked, because these are in the top row and are clearly outside the boundary. Similarly, the lattice points next to F and H need not be checked.

Lattice point c is checked next. The nearest boundary vertex "below" c is F, and the nearest one "above" c is A. The program looks at angle FcA. This angle bends to the right, because c is outside the boundary. Since this is the only neighboring lattice point along the left edge, the left boundary is okay.

Next, lattice point e is checked. The boundary vertex "above" e is B, and the one "below" e is H. The program looks at angle BeH. This angle does not bend at all, because e lies right on the boundary. Since e is on the boundary, it is part of the convex hull (a set that includes both the boundary and its interior). The original polyomino is rejected: it is not a convex-hull polyomino.

Program Output: Orders 6, 7 and 8

There are 25 convex-hull hexominoes (N=6):

There are 48 convex-hull heptominoes (N=7):

There are 107 convex-hull octominoes (N=8):

o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o

The Inductive Algorithm

Generating all the polyominoes and then testing them to see if they are of the convex-hull type (as described above) gets to be a rather time-consuming process. For N=14, there are 901971 polyominoes and only 2777 of these are convex-hull. If we are only trying to count the convex-hull polyominoes, we want something a lot more efficient.

Fortunately, there is a way to derive every convex-hull polyomino of a given order (say order 8) from the convex-hull polyominoes of the next smaller order. One merely needs to try all the ways of adding a square to an existing order-7 convex-hull polyomino and test each result to see if it qualifies.

This is a bit hard to show directly: Where do you add the new point? How do you know the result will still be convex?

Instead of trying to prove that they can be built up, it is actually easier to prove the opposite statement:

Given any convex-hull polyomino of order greater than one, it is always possible to find a point which, if removed, yields a convex-hull polyomino of the next smaller order.

To see that this is true, one needs to consider just the top row, and imagine removing just the rightmost or just the leftmost point on that row. After removing the point, adjust the convex hull. When doing this adjustment, the convex hull will "give up territory" but in no case does it gain any territory. Therefore, there are no new lattice points that are encompassed by the new (smaller) convex hull.

Here are examples of each of the possibilities:

One Point in Top Row

If there is just one lattice point in the top row, it will be like one of these four cases:

. A . . A . . A . . A . o | o /| o |\ o / \ o . B . o . / B . o . B \ . o . / B \ . o | o o / | o o | \ o o o / \ . C . D---C . . C---E D---C---E Case 1A Case 1B Case 1C Case 1D

In all of these cases, the single point in the top row is removed to make a smaller convex-hull polyomino.

Case 1A is a "linear" polyomino where all the points are on a line, and the convex hull is a line segment. Removing point A makes it a shorter line segment.

In case 1B, the convex hull is triangle ACD. When point A is removed, triangle ABD is removed with it, and the convex hull becomes triangle BCD.

Case 1C is just a mirror image of case 2. Triangle AEB is removed, and the convex hull shrinks from AEC to BEC.

In case 1D, the convex hull starts out as triangle AED. When point A is removed, triangles ABD and AEB are both removed with it, and the convex hull shrinks to triangle BED.

Two or More Points in Top Row: Overhang Cases

If there is more than one point in the top row, there are several cases to consider. First consider the cases where there is a point at one end of the top row, with no point below it. The top row can be said to "overhang" the row below it.

A---B . A---B . A---B---* o o \ \ o o \ | o o o \ / o . \ C \ . o . \ C . o . \ C / . o o \ \ o \| o \ / . D---* . D . . D . Case 2A Case 2B Case 2C

In all of these cases, point A can be removed to make a smaller convex-hull polyomino. In all cases pictured, triangle ABD is removed from the convex hull.

Sometimes the changes to the convex hull are a little more complex, like this example:

A---B---* . B---* \ | | | o o o . \ C * o o . C * o o \ | o o \ | o . .\ * o . . \ * o \ | o \| . . D . . D before after

In this example, when point A is removed, the areas inside triangle ABC and triangle ACD are both removed from the convex hull.

Two or More Points in Top Row: Non-Overhang Cases

If there is a point in the second row below every point in the top row, then a point can be removed from either end of the top row to create a smaller convex-hull polyomino. This example illustrates what happens:

. A---B . . . .B . . A. . . | \ / \ | \ o o . C D . o . C' D . o . C `D . o o | \ o o | \ o o | \ o o . E F . o o . E F . o o . E F \ . o o o | \ o o o | \ o o o | \ . G---H---I . G---H---I . G---H---I before after removing A after removing B

If point A is removed from the polyomino, triangle ABC is removed from the convex hull.

If instead point B is removed from the polyomino, triangles ABD and BID are both removed from the convex hull.

Conclusion

As shown by the above examples, it is always possible to remove a point from the top row of a convex-hull polyomino, forming a smaller polyomino whose convex hull is a proper subset of the original. Since the new convex hull is a subset of the old one, there are no lattice points that get added to the interior of the convex hull. Since no new lattice points are added, the new polyomino still satisfies the definition of a convex-hull polyomino.

Since every convex hull polyomino can be "reduced" by one square to make another smaller one, it follows that you can discover all convex-hull polyominoes of order N+1 by trying all ways to add a single square to all convex-hull polyominoes of order N.

(For a similar proof regarding another "hard" counting problem, see my A005656 page.)

Growth Trends

As N increases, the number of convex-hull polyominoes is an ever-smaller fraction of all polyominoes. For N=5, as shown above, we have 10 out of 12: 83 percent. For N=6 the ratio is 25 out of 35, and for N=7 it is less than half: 48 out of 108. At N=14 there are only 2777 convex-hull polyominoes out of a total of 901971: less than one in 300.

Wechsler has pointed out to me the unusual "odd-even" pattern in the growth rate of the sequence, evident in the finite differences. Here again is the sequence:

1, 1, 2, 5, 10, 25, 48, 107, 193, 365, 621, 1082, 1715, 2777, 4247, 6519, ...

These are its first and second differences:

0, 1, 3, 7, 15, 23, 59, 86, 172, 256, 461, 633, 1062, 1470, 2272, ...

1, 2, 4, 8, 8, 36, 27, 86, 84, 205, 172, 429, 408, 802, ...

The second differences show the uneven growth rate. This suggests that a parity effect (such as the ratio of black to white squares when the polyonimo is checkerboard-colored) plays a role in the convex property.

The Disk Polyominoes

Related to the convex-hull polyominoes are a much less numerous class, also studied by Wechsler and counted by Sloane's A147680. A polyomino is called a disk polyomino (or "disklike") if and only if you can draw a circle that touches or encloses all its lattice points without touching or enclosing any other lattice points.

Given a polyomino P on a square lattice, if you replace each of the squares in P with a point (e.g. its top-left corner) and call that set of points S :
The polyomino is said to be a disk polyomino if and only if there exists a disk D such that the intersection of D with the lattice is equal to S.

There are not very many disk polyominoes of any given order. Here are all up to order 12; the numbers are sequence A147680 :

o o o o o o o o o o o o o o o o o o o o o 1 1 o o o 1 2 2 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 2 1 2 2 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 3 3 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 4

Sequence A181785, Wechsler's Convex-Hull Polyominoes

Introduction

Definition

Convex-Hull Examples

Enumerating the Convex-Hull Polyominoes

Program Output: Orders 6, 7 and 8

The Inductive Algorithm

Growth Trends

The Disk Polyominoes

See Also