{"id":687,"date":"2018-02-02T11:09:19","date_gmt":"2018-02-02T19:09:19","guid":{"rendered":"http:\/\/puzzlezapper.com\/blog\/?p=687"},"modified":"2018-02-02T11:09:19","modified_gmt":"2018-02-02T19:09:19","slug":"vexed-by-convexity","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2018\/02\/vexed-by-convexity\/","title":{"rendered":"Vexed by Convexity, part one"},"content":{"rendered":"

Last September I came across a conversation<\/a> on Twitter about how convex the 12 pentominoes are. At first glance, this might seem like an uninteresting problem. Clearly, the I pentomino is convex, and the rest aren’t. (Recall that a shape is convex if, for any pair of points inside the shape, the segment connecting them is entirely within the shape. Otherwise, we call it concave.)<\/p>\n

But the problem wasn’t whether<\/em> the pentominoes are convex, but how<\/em> convex they are. In order to answer that, we’d like a measure that gives 1 for a shape that is convex, and ranges between 0 and 1 for concave shapes, getting higher as they more closely resemble some convex shape.<\/p>\n

There are several measures that work. (For a discussion of convexity measures, see this paper<\/a> by J. Zunic and P. Rosen.) One strategy for measuring convexity is to consider a shape in relation to its convex hull<\/em>. A shape’s convex hull is the smallest convex shape it is contained in. Naturally, a convex shape is its own convex hull. The ratio of the area of a shape to that of its convex hull makes a reasonable measure of convexity. Or instead of areas, we could instead look at perimeters. The perimeter of a shape can never be less than that of its convex hull. So the ratio of a shape’s convex hull’s perimeter to that of the shape itself can also be used as a convexity measure. <\/p>\n

Another method of measuring convexity is the probability that the segment between two points in a shape chosen at random lies entirely within the shape. Finding exact values for this measure can involve some tricky math, which Dan Piponi worked through for the P pentomino<\/a>. However, calculating an estimate by randomly picking a large number of pairs of points is also an option. And, as it happens, Rod Bogart did exactly that<\/a>.<\/p>\n

The following table shows the convexities of the pentominoes according to each of these three measures.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Pentomino, shown with convex hull<\/td>\nArea \/ Convex Hull Area<\/td>\nConvex Hull Perimeter \/ Perimeter<\/td>\nProbabilistic method<\/td>\n<\/tr>\n
\"\"<\/td>\n.7143<\/td>\n.8387<\/td>\n.786<\/td>\n<\/tr>\n
\"\"<\/td>\n1<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n
\"\"<\/td>\n.7692<\/td>\n.9302<\/td>\n.822<\/td>\n<\/tr>\n
\"\"<\/td>\n.7692<\/td>\n.8875<\/td>\n.778<\/td>\n<\/tr>\n
\"\"<\/td>\n.9091<\/td>\n.9414<\/td>\n.946<\/td>\n<\/tr>\n
\"\"<\/td>\n.7143<\/td>\n.8726<\/td>\n.788<\/td>\n<\/tr>\n
\"\"<\/td>\n.8333<\/td>\n.8333<\/td>\n.708<\/td>\n<\/tr>\n
\"\"<\/td>\n.7143<\/td>\n.9024<\/td>\n.748<\/td>\n<\/tr>\n
\"\"<\/td>\n.7692<\/td>\n.8536<\/td>\n.772<\/td>\n<\/tr>\n
\"\"<\/td>\n.7143<\/td>\n.8047<\/td>\n.840<\/td>\n<\/tr>\n
\"\"<\/td>\n.7692<\/td>\n.8875<\/td>\n.854<\/td>\n<\/tr>\n
\"\"<\/td>\n.7143<\/td>\n.8726<\/td>\n.720<\/td>\n<\/tr>\n<\/table>\n

Convex hull area method data by Vincent Pantaloni. Convex hull perimeter method data mine. Probabilistic method data by Ron Bogart.<\/em><\/p>\n

Even though these shapes are pretty simple, the data above shows that the different convexity measures treat them differently in interesting ways. Notice that the X pentomino, for example, is tied for the least convex pentomino by the convex hull area method, but is the fourth most<\/em> convex by the probabilistic method.<\/p>\n

I hope I’ve shown that convexity, as applied to polyominoes, is more interesting than it might have seemed! In part two, I’ll look at how we can use these convexity measures to make some new puzzles.<\/p>\n","protected":false},"excerpt":{"rendered":"

Last September I came across a conversation on Twitter about how convex the 12 pentominoes are. At first glance, this might seem like an uninteresting problem. Clearly, the I pentomino is convex, and the rest aren’t. (Recall that a shape is convex if, for any pair of points inside the shape, the segment connecting them … Continue reading Vexed by Convexity, part one<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[194,10,33],"class_list":["post-687","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-convexity","tag-pentominoes","tag-tetrominoes"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/687","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/comments?post=687"}],"version-history":[{"count":14,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/687\/revisions"}],"predecessor-version":[{"id":718,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/687\/revisions\/718"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=687"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=687"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=687"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}