triangulate point configurations

[vbraun]

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.

CC: @sagetrac-mhampton @novoselt

Component: geometry

Author: Volker Braun

Reviewer: Marshall Hampton

Merged: sage-4.6.2.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/9918

[sagetrac-mhampton]

comment:2

Passes tests, coverage, documentation looks good. Nice work! I haven't tested with TOPCOM but I don't think that's necessary since everything works without it.

[sagetrac-mhampton]

Reviewer: Marshall Hampton

[novoselt]

comment:4

For the record:

/disk/scratch/novoselt/sage/devel/sage/doc/en/reference/sage/geometry/triangulation/point_configuration.rst:638: WARNING: duplicate citation BSS, other instance in /disk/scratch/novoselt/sage/devel/sage/doc/en/reference/sage/geometry/polyhedra.rst

I am not sure what we are supposed to do with this (personally, I like to have references in the file where they are referenced), but the documentation does not build without warnings...

[vbraun]

comment:5

See also:

https://groups.google.com/d/topic/sage-devel/26YSkYOztus/discussion

Until there is a proper way of dealing with duplicate references, I think it is best to keep the warning around. The alternatives all suck...

[jdemeyer]

comment:6

Replying to @novoselt:

For the record:

/disk/scratch/novoselt/sage/devel/sage/doc/en/reference/sage/geometry/triangulation/point_configuration.rst:638: WARNING: duplicate citation BSS, other instance in /disk/scratch/novoselt/sage/devel/sage/doc/en/reference/sage/geometry/polyhedra.rst

I am not sure what we are supposed to do with this (personally, I like to have references in the file where they are referenced), but the documentation does not build without warnings...

I'm afraid a Sphinx warning is sufficient reason for needs_work...

[vbraun]

Attachment: trac_9918_triangulate_point_configurations.patch.gz

Updated patch

[vbraun]

comment:7

Fine, if lack of warnings is more important than usefulness of the documentation. I removed the text of the citation, leaving only the link to the same citation a different module. Now Sphinx doesn't complain any more.

[jdemeyer]

Merged: sage-4.6.2.alpha3