Re: [math-fun] Convex polyominoes
Given a closed & bounded convex figure K: Does "intersection between any convex figure and the lattice" mean the union of grid squares that intersect K ? Or the union of grid squares that are each entirely contained in K ? (Or maybe both definitions yield the same set of polyominoes?) * * * Allan's definitions of disklike polyomino, and the one below, suggest another one: * A polyomino that is topologically a closed disk. (E.g., this would exclude the ringlike heptomino O_7.) This would include all n-ominoes through n = 6, but then things start to get interesting. (A perhaps nicer variant would be to require only that the *open* polyomino be a topological disk. This would rescue O_7.) * * * I like hexagonal polyominoes -- say, "heximoes" -- since no two cells can overlap on just a vertex, thus avoiding borderline cases like H_7. Here the topological-disk ones exclude n-heximoes only for n >= 6. QUESTION: Is there a simple asymptotic expression H(n) for the number of topological-disk n-heximoes? (In 3-space one could likewise ask for topological-3-disks tesssellated by truncated octahedral tiles, and an asymptotic formula for their counts, etc.) --Dan --------------------------------------------------------------- Allan wrote: << 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.
Sometimes the brain has a mind of its own.
I am thinking of all of these polyominoes as sets of lattice-points, that is, points with integer coordinates. It is these points which I wanted to cover with a disk in the earlier disklike case, and it is these points whose convex hull I am taking, and insisting that no additional lattice points are thereby encompassed. The hexagon case already has a traditional name, *polyhexes*. On Sat, May 7, 2011 at 1:38 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Given a closed & bounded convex figure K:
Does "intersection between any convex figure and the lattice" mean the union of grid squares that intersect K ?
Or the union of grid squares that are each entirely contained in K ?
(Or maybe both definitions yield the same set of polyominoes?)
* * *
Allan's definitions of disklike polyomino, and the one below, suggest another one:
* A polyomino that is topologically a closed disk.
(E.g., this would exclude the ringlike heptomino O_7.)
This would include all n-ominoes through n = 6, but then things start to get interesting.
(A perhaps nicer variant would be to require only that the *open* polyomino be a topological disk. This would rescue O_7.)
* * *
I like hexagonal polyominoes -- say, "heximoes" -- since no two cells can overlap on just a vertex, thus avoiding borderline cases like H_7.
Here the topological-disk ones exclude n-heximoes only for n >= 6.
QUESTION: Is there a simple asymptotic expression H(n) for the number of topological-disk n-heximoes?
(In 3-space one could likewise ask for topological-3-disks tesssellated by truncated octahedral tiles, and an asymptotic formula for their counts, etc.)
--Dan
--------------------------------------------------------------- Allan wrote:
<< 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.
Sometimes the brain has a mind of its own.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The way I interpreted the original question, based on Allan's description and his proposed sequence 1, 1, 2, 5, 10, 25 was: Given a polyomino P on a square lattice, if you replace each of the squares in P with a point (say the "upper-left" corner) and call that set of points S, and then define H to be the convex hull of S, then the polyomino is said to be "disklike" if all lattice points in H are also in S. Since my previous message I took a nap and then decided to give up figuring out the whole thing myself. Since I am taking a convex hull of points aligned on a lattice the algorithm is a lot simpler than the general case, it seems I need little more than a test for whether an angle ABC is less than or greater than 180 degrees (e.g. the determinant formula for the signed area of a triangle, see http://mathworld.wolfram.com/TriangleArea.html formulas 16 and 17). I can start by confirming that each "row" of the polyomino is a single contiguous run of squares (rejecting the U pentomino in "horizontal" orientation, and all polyominoes with holes A001419). Then I can use the left and right ends of each row to define a set of points which is a superset of the convex hull, and the ABC angle test (walking up the left side of the polyomino, and walking down the right side) to eliminate points that are not one of the "vertices" of the convex hull. Finally I can look at the lattice points closest to the extreme ends of each row (except the first and last) to determine if they are within the hull. That test would reject the V pentomino (whose convex hull is a right triangle), on the basis that its middle row contains a single lattice point, one of whose neighbors falls on the hypotenuse. On Sat, May 7, 2011 at 13:38, Dan Asimov <dasimov@earthlink.net> wrote:
Given a closed & bounded convex figure K:
Does "intersection between any convex figure and the lattice" mean the union of grid squares that intersect K ?
Or the union of grid squares that are each entirely contained in K ?
(Or maybe both definitions yield the same set of polyominoes?)
* * *
Allan's definitions of disklike polyomino, and the one below, suggest another one:
* A polyomino that is topologically a closed disk.
[...]
Allan wrote:
<< 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.
Sometimes the brain has a mind of its own.
--
Robert Munafo -- mrob.com Follow me at: fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com- youtube.com/user/mrob143 - rilybot.blogspot.com
I have now implemented the "disklike polyomino" algorithm (as described in my previous message) and the automatically generated results agree with Allan's proposed sequence. I have verified A(6)=25 and A(7)=48 by visual inspection of the 35 hexominoes and 108 heptominoes. For N=1 through 13, my program computes: 1, 1, 2, 5, 10, 25, 48, 107, 193, 365, 621, 1082, 1715 I have submitted this sequence to OEIS as A181785 <http://oeis.org/A181785>. I have also created a web page for the sequence, which includes pictures of the "disklike" polyominoes for N=6 and N=7. On Sat, May 7, 2011 at 17:48, Robert Munafo <mrob27@gmail.com> wrote:
The way I interpreted the original question, based on Allan's description and his proposed sequence 1, 1, 2, 5, 10, 25 was:
Given a polyomino P on a square lattice, if you replace each of the squares in P with a point (say the "upper-left" corner) and call that set of points S, and then define H to be the convex hull of S, then the polyomino is said to be "disklike" if all lattice points in H are also in S.
[...]
-- Robert Munafo -- mrob.com Follow me at: fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com- youtube.com/user/mrob143 - rilybot.blogspot.com
I forgot to give a link -- my web page for the sequence is here: http://mrob.com/pub/math/seq-a181785.html On Sun, May 8, 2011 at 01:59, Robert Munafo <mrob27@gmail.com> wrote:
I have now implemented the "disklike polyomino" algorithm [...]
1, 1, 2, 5, 10, 25, 48, 107, 193, 365, 621, 1082, 1715
I have submitted this sequence to OEIS as A181785<http://oeis.org/A181785> .
I have also created a web page for the sequence, which includes pictures of the "disklike" polyominoes for N=6 and N=7.
-- Robert Munafo -- mrob.com Follow me at: fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com- youtube.com/user/mrob143 - rilybot.blogspot.com
Interesting that the ratio of consecutive terms seems to be < 2, while the ratio for ordinary polyominos is (likely) > 4. Rich ----- Quoting Robert Munafo <mrob27@gmail.com>:
I forgot to give a link -- my web page for the sequence is here:
http://mrob.com/pub/math/seq-a181785.html
On Sun, May 8, 2011 at 01:59, Robert Munafo <mrob27@gmail.com> wrote:
I have now implemented the "disklike polyomino" algorithm [...]
1, 1, 2, 5, 10, 25, 48, 107, 193, 365, 621, 1082, 1715
I have submitted this sequence to OEIS as A181785<http://oeis.org/A181785> .
I have also created a web page for the sequence, which includes pictures of the "disklike" polyominoes for N=6 and N=7.
-- Robert Munafo -- mrob.com Follow me at: fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com- youtube.com/user/mrob143 - rilybot.blogspot.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Wouter: We're just in two dimensions at this point; the 3D convex hull problem is much more challenging! Rich: Robert and I are having some backchannel chat about the growth rate. I anticipated that the growth rate might be much slower than that for unrestricted polyominoes, because the convexity constraint imposes lots of local forbidden configurations, which almost all unrestricted polyominoes would be expected to have. If you want to see something amusing and hard to think about, which I did *not* expect, look at the second differences of the sequence Robert gave. See if you can explain the very marked period-2 oscillation. Robert has some ideas about that which I haven't read carefully yet. On Mon, May 9, 2011 at 4:12 PM, <rcs@xmission.com> wrote:
Interesting that the ratio of consecutive terms seems to be < 2, while the ratio for ordinary polyominos is (likely) > 4.
Rich
-----
Quoting Robert Munafo <mrob27@gmail.com>:
I forgot to give a link -- my web page for the sequence is here:
http://mrob.com/pub/math/seq-a181785.html
On Sun, May 8, 2011 at 01:59, Robert Munafo <mrob27@gmail.com> wrote:
I have now implemented the "disklike polyomino" algorithm [...]
1, 1, 2, 5, 10, 25, 48, 107, 193, 365, 621, 1082, 1715
I have submitted this sequence to OEIS as A181785< http://oeis.org/A181785>
.
I have also created a web page for the sequence, which includes pictures of the "disklike" polyominoes for N=6 and N=7.
-- Robert Munafo -- mrob.com Follow me at: fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com- youtube.com/user/mrob143 - rilybot.blogspot.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Allan Wechsler -
Dan Asimov -
rcs＠xmission.com -
Robert Munafo