Ask Your Question
1

Randomly generated simple polytopes with given number of vertices

asked 2016-01-29 00:08:43 +0100

guillermo gravatar image

updated 2016-02-04 11:13:56 +0100

tmonteil gravatar image

Hi there,

I wonder if there is a way of generating random simple polytopes with a given number of vertices.

EDIT

By "random" I simply mean constructing a polytope by sampling points on the unit sphere.

A simple d-polytope is a d-polytope in which every vertex is part of precisely d facets, or equivalently, of precisely d edges.

Thank you, and regards, Guillermo

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2016-01-29 15:23:34 +0100

tmonteil gravatar image

updated 2016-02-04 11:17:24 +0100

As far as i know, there is no canonical measure on the set of polytopes with a given number of vertices. So, you need to provide what "random" means for you. Otherwise, here is a basic rejection algorithm:

def random_polytope(npoints=4, dimension=3, ring=RDF):
    while True:
        P = Polyhedron(vertices=[(ring.random_element() for i in range(dimension)) for n in range(npoints)])
        if P.n_vertices() == npoints:
            return P

Then, you can do:

sage: random_polytope(10,3)
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 10 vertices

Note that when the dimension is small and the number of points is big, you might wait a long time since in most cases, one of the points will be contained in the convex hull of the others.

EDIT

Here is how to make a polytope from points uniformly sampled on the unit sphere: it suffice to take vectors whose coordinates are sampled independently accorfing to the normal distribution and then project them on the sphere:

def random_polytope(npoints=4, dimension=3):
    vert = []
    for i in range(npoints):
        v = vector((gauss(0,1) for d in range(dimension)))
        v = v / v.norm()
        vert.append(v)
    return Polyhedron(vertices=vert)

Then you can do:

sage: p = random_polytope(npoints=100, dimension=3)
sage: p.plot()
Launched jmol viewer for Graphics3d Object

If you want to sample simple d-polytope from this, you can use a rejection algorithm as before.

edit flag offensive delete link more

Comments

Dear Thierry,

Thank you very much for your response. By "random" I simply mean constructing a polytope is by sampling points on the unit sphere.

My question is however about generating simple polytopes. A simple d-polytope is a polytope in which every vertex is part of precisely d facets, or equivalently, of precisely d edges. The polytopes you generate are most likely not simple; in fact, they are most likely simplicial, that is, every facet is a simplex. While a dual of a simplicial polytope is a simple polytope, I need the number of vertices in the simple polytope not in the simplicial one.

Thank you, once again, and regards, Guillermo

guillermo gravatar imageguillermo ( 2016-02-04 00:48:23 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-01-29 00:08:43 +0100

Seen: 1,131 times

Last updated: Feb 04 '16