#9918: triangulate point configurations
----------------------------+-----------------------------------------------
Reporter: vbraun | Owner: mhampton
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6
Component: geometry | Keywords:
Author: Volker Braun | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
The attached patch implements triangulations of point configurations in
arbitrary dimensions in Sage/Cython/C++ without relying on TOPCOM.
{{{
sage: points = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]);
sage: points
A point configuration in QQ^2 consisting of 5 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
sage: triang = points.triangulate() # find one triangulation
sage: triang
(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)
sage: triang[0]
(0, 1, 2)
sage: list( points.triangulations() )
[(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>),
(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>),
(<1,2,3>, <1,2,4>),
(<1,3,4>, <2,3,4>)]
sage: triang.plot(axes=False)
}}}
The internal implementation covers finding a single triangulation as well
as enumerating all triangulations connected to it by bistellar flips.
TOPCOM is required to test for regularity and/or to find non-connected
triangulations.
While not quite as fast, my limited testing shows the performance to be in
the same order of magnitude as TOPCOM:
{{{
sage: U=matrix([
... [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0],
... [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0],
... [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1],
... [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1],
... [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0]
... ])
sage: pc = PointConfiguration(U.columns())
sage: pc.set_engine('internal')
sage: time len(pc.triangulations_list())
CPU times: user 23.26 s, sys: 0.02 s, total: 23.29 s
Wall time: 23.32 s
9623
sage: pc.set_engine('TOPCOM')
sage: time len(pc.triangulations_list())
CPU times: user 7.80 s, sys: 0.13 s, total: 7.93 s
Wall time: 8.37 s
9623
}}}
See also #8169: include TOPCOM, where an optional spkg is being worked on.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9918>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
