#18442: Implement a barycentric subdivision method for Polyhedron class
-------------------------------------+-------------------------------------
Reporter: jipilab | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.8
Component: geometry | Resolution:
Keywords: polytope, | Merged in:
barycentric subdivision | Reviewers:
Authors: Jean-Philippe | Work issues:
Labbé | Commit:
Report Upstream: N/A | a0124fb056aa8880f1b85af7ff095fa74fabb936
Branch: | Stopgaps:
public/ticket/18442 |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by jipilab):
Hi again,
So, I looked at bit at the literature, maybe I'm missing some efficient
way to compute it...
Suppose we have a very round polytope and we want to do the barycentric
subdivision of it. To do it, I used the face fan of the polar (which is
the normal fan of the original) for the implementation since cutting by an
hyperplane was algorithmically easier than adding a vertex (as I saw
it...).
We need to start with adding a vertex at the barycenter of all the facets.
This is done dually by chopping every vertex of the polar polytope. The
"chopping height" is determined by the location of the vertices of the
polytope: we cut 1/3 of the shortest edge touching this vertex in the
direction of the normal of the hyperplane.
Once all the facets are done, we really need (I believe) to compute an
intermediate polytope to proceed to the ridges and lower dimensional faces
to subdivide, since the location of the next cuts will depend on the
location of the newly created vertices (remember that the polytope is
assumed very round so the interval in which we can put the next vertices
depend highly on the previous ones).
Topologically, this is not necessary, but to realize the barycentric
subdivision convexly I'm afraid this is necessary.
In any case, I believe that the barycentric subdivision is known to be
very costly (counting flags in a lattice grows exponentially...) so it is
to be expected that it gets slow very fast. Of course, it also depends in
which ring the computation is done.
Does the way I used make sense at all?
--
Ticket URL: <http://trac.sagemath.org/ticket/18442#comment:16>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
