ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 03 Feb 2016 17:48:23 -0600Randomly generated simple polytopes with given number of verticeshttp://ask.sagemath.org/question/32366/randomly-generated-simple-polytopes-with-given-number-of-vertices/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 Thu, 28 Jan 2016 17:08:43 -0600http://ask.sagemath.org/question/32366/randomly-generated-simple-polytopes-with-given-number-of-vertices/Answer by tmonteil for <p>Hi there,</p>
<p>I wonder if there is a way of generating random simple polytopes with a given number of vertices. </p>
<p><strong>EDIT</strong></p>
<p>By "random" I simply mean constructing a polytope by sampling points on the unit sphere.</p>
<p>A simple d-polytope is a d-polytope in which every vertex is part of precisely d facets, or equivalently, of precisely d edges. </p>
<p>Thank you, and regards,
Guillermo </p>
http://ask.sagemath.org/question/32366/randomly-generated-simple-polytopes-with-given-number-of-vertices/?answer=32377#post-id-32377As 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.
Fri, 29 Jan 2016 08:23:34 -0600http://ask.sagemath.org/question/32366/randomly-generated-simple-polytopes-with-given-number-of-vertices/?answer=32377#post-id-32377Comment by guillermo for <p>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:</p>
<pre><code>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
</code></pre>
<p>Then, you can do:</p>
<pre><code>sage: random_polytope(10,3)
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 10 vertices
</code></pre>
<p>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.</p>
<p><strong>EDIT</strong></p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>Then you can do:</p>
<pre><code>sage: p = random_polytope(npoints=100, dimension=3)
sage: p.plot()
Launched jmol viewer for Graphics3d Object
</code></pre>
<p>If you want to sample simple d-polytope from this, you can use a rejection algorithm as before.</p>
http://ask.sagemath.org/question/32366/randomly-generated-simple-polytopes-with-given-number-of-vertices/?comment=32434#post-id-32434Dear 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,
GuillermoWed, 03 Feb 2016 17:48:23 -0600http://ask.sagemath.org/question/32366/randomly-generated-simple-polytopes-with-given-number-of-vertices/?comment=32434#post-id-32434