Parametrization of polygons and polyhedra [closed]

Question

So, I've got a pretty interesting problem:

I was wondering how one would go about trying to generate every n-gon, or at least parametrize the space of a specific n-gon (say a hexagon) so it's easily spanned.

For instance, what are the best variables to define an n-gon such that one could easily cycle through them with a loop.

And then, how would one do this with polyhedra? One constraint is that all the shapes should have the same area/volume.

For some perspective, I'm currently running some physics computations that take in polyhedral meshes and output physical characteristics for each mesh, and we need to have a good way of cycling through the shapes.

Answer 1

One route, perhaps not appropriate for your application because of the area constraint (see end of this post), is to fix a set $S$ of $n$ points in the plane, and then walk among all the (in general exponentially many) different simple polygonalizations $P$ of $S$. I coauthored one paper on this myself:

Damian, Mirela, Robin Flatland, Joseph O’Rourke, and Suneeta Ramaswami. "Connecting polygonizations via stretches and twangs." Theory of Computing Systems 47, no. 3 (2010): 674-695. (Pre-journal arXiv abstract.)

---

         

---

More generally, a nice (but now out-of-date) web page on generating random polygons was maintained by Jeff Erickson here.

There is less work on polyhedralizations of fixed point sets, or random (not necessarily convex) polyhedra in $\mathbb{R}^3$. Here is one reference:

Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54. (PDF download pre-journal version.)

If generating random convex polyhedra suffices for your purposes, there are many approaches. See, e.g.,

Schneider, Rolf. "Recent results on random polytopes." Boll. Unione Mat. Ital.(9) 1.1 (2008): 17-39. (PDF download pre-journal version.)

I think achieving your constant area/volume constraint will be challenging. For example, finding a polygonization of minimum area of a fixed point set is NP-hard.