If I have a grid made of equilateral triangles, I can easily form larger convex polygons as a set of tiles in that grid. I believe this holds for some (but not all) tilings of non-equilateral triangles.

The same for quadrilaterals - it's obvious for squares, rectangles and parallelograms, but I believe it also holds for some other (but not all) tilings of quadrilaterals.

I'm pretty sure tiling a flat area purely with convex pentagons is impossible, so skip that case.

With hexagons, a tiled grid is possible, but the only way to make a convex polygon from those convex hexagonal tiles seems to be to use only one tile - no multi-tile convex polygons seem possible.

My speculation is that it's only possible to form a multi-tile convex polygon from convex polygon tiles if all those tiles have interior angles at all vertices of 90 degrees or less, at least for those vertices that are at a vertex or edge of that larger convex polygon.

Is that speculation correct? Is there a proof or disproof?


Are you looking for items like the Hirschhorn Medallion?

Hirschhorn Medallion

  • $\begingroup$ Very nice, but no. The idea started when I was reading a blog post about pathfinding in square grids, and I wondered how far I could generalise to different grids. I thought about an idea I had some time ago about defining cells for the pathfinding to work on where each cell was as large as possible while being convex (so any point within a cell could be reached from any other in one step - I also had a variant where any point could be reached from any other in two steps via a centre point). $\endgroup$ – Steve314 May 23 '13 at 2:27
  • $\begingroup$ The two pathfinding ideas are separate anyway. Tthe whole point of defining convex cells is that there are no pre-defined cells, and the whole point of the two-step non-convex cells is to cope with e.g. circular barriers - if everything is defined on a square/whatever grid these should be non-issues. Basically, I was just going off on a random tangent. maybe thinking about optimising pathfinding on a grid by combining cells. Though this certainly shows a case where larger convex cells are possible, but can't be found by growing incrementally larger convex cells. $\endgroup$ – Steve314 May 23 '13 at 2:37

Sorry - I figured it out within a minute of posting. Should have thought longer before asking.

If two polygons are joined such that such that a vertex and edge are on the same point and line, there are two cases...

  • If the sum of the two interior angles is greater than 180 degrees, this is a concavity. It's only valid as part of a larger convex polygon if that concavity is filled by more tiles.

  • If the sum of the two interior angles is less than or equal to 180 degrees, there is no concavity. This vertex may be at the vertex or edge of a larger convex polygon formed from these tiles.

So the issue is the sum of the angles, not the interior angle at the vertex of one particular tile.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.