Robert, 2D or 3D lattice? Wouter ----- Original Message ----- From: "Robert Munafo" <mrob27@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Saturday, May 07, 2011 6:35 PM Subject: Re: [math-fun] Convex polyominoes

My program is correctly generating the polyominoes (verified by comparing counts to A000105), but I'm stuck (in my mind) on how to derive the convex hull and how to test other points in the grid to see of they are inside or outside the convex hull. Once I know which points define the vertices of the convex hull, I could use the Jordan Curve theorem for testing other points, but when a point falls right on the boundary I have to worry about round-off error.

Any hints?

Allan Wechsler 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.

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.

-- 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

__________ NOD32 6102 (20110507) Informatie __________

Dit bericht is gecontroleerd door het NOD32 Antivirus Systeem. http://www.nod32.nl

I have to confess that in the interim between my posting this problem and now, I've gone off the problem a bit. What disillusioned me was realizing that although disklike collections of lattice-points are *automatically*polyominoes, "convex" collections can easily be disconnected. It means that these objects have two independent constraints (lattice connectedness, lattice convexity), which makes them seem less elegant to me. But, having started this ... Any computational geometry book will have at least a section on convex hull algorithms. The one on the bookshelf over my screen is Preparata and Shamos, *Computational Geometry*, Springer, 1985; chapter 3 is devoted to the question. The problem is really a question of doing it *efficiently*. A stupid brute-force algorithm is easy: the convex hull is the union of the hulls of all three-point subsets of the given point-set. On Sat, May 7, 2011 at 12:35 PM, Robert Munafo <mrob27@gmail.com> wrote:

My program is correctly generating the polyominoes (verified by comparing counts to A000105), but I'm stuck (in my mind) on how to derive the convex hull and how to test other points in the grid to see of they are inside or outside the convex hull. Once I know which points define the vertices of the convex hull, I could use the Jordan Curve theorem for testing other points, but when a point falls right on the boundary I have to worry about round-off error.

Any hints?

Allan Wechsler 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.

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.

-- 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