Polytope triangulation fails sometimes on polytopes with non-precise vertices

[Günter Rote]

Example 1.

P1=Polyhedron(backend='cdd', base_ring=RDF, vertices=[(RDF(1), -RDF(1), RDF(0)), (RDF(1), -RDF(1), RDF(1)), (RDF(1), RDF(1), RDF(1)), (RDF(1), RDF(1), -RDF(1)), (RDF(0), RDF(1), -RDF(1)), (RDF(1), RDF(0.33333333329999998), -RDF(1)), (-RDF(1), RDF(1), RDF(1)), (-RDF(1), RDF(1), -RDF(0.5)), (-RDF(1), -RDF(1), RDF(1))]);P1

A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 9 vertices

P1.triangulate() leads to "ZeroDivisionError: input matrix must be nonsingular"

I tried it on https://cocalc.com/ which runs SageMath version 9.1

=======================================

Example 2.

P2=Polyhedron(backend='cdd', base_ring=RDF, vertices=[(-RDF(0.1113445378),

-RDF(0.55567226889999999), RDF(1)), (RDF(1.0063025210000001),
-RDF(0.49684873950000003), RDF(0)), (RDF(1), RDF(0), RDF(1)), (RDF(2),
RDF(0), RDF(0)), (-RDF(0.56836734690000001), -RDF(0.13673469390000001),
RDF(1)), (-RDF(0.53979591839999996), RDF(0.92040816329999997), RDF(0)),

(RDF(0), RDF(1), RDF(1)), (RDF(0), RDF(2), RDF(0))])

A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 8 vertices

P2.triangulate()

gives

(<0,1,3,4>, <0,2,3,6>, <0,3,4,6>, <1,3,4,7>, <1,4,5,7>, <3,4,6,7>, <4,5,6,7>)

on https://cocalc.com/, but it fails with "ZeroDivisionError: input matrix must be nonsingular" on my Sage 8.9 installation on my home computer.

==========================

The polytopes were obtained by giving inequalities with float coefficients. (intersections of half-spaces). Plotting them works fine.

These bugs affect also the volume() and centroid() methods.

[Dima Pasechnik]

Sage 8.9 is old, and cdd was updated in Sage since then.
Your best bet is to upgrade Sage, and most likely these bugs will go
away (e.g. this works well in Sage 9.2.beta13).

Having said that, as you most probably know,
a much more robust way to compute with polyhedra in Sage is to use
exact rational arithmetic; things like triangulations,
facet enumeration, etc, are unstable if one uses RDF, i.e. CPU floats
(and thus precision might be lost).
E.g. for your 1st example, why not just do

sage: P1=Polyhedron(vertices=[(1, -1,0), (1, -1,1), (1,1,1), (1,1,
-1), (0,1,-1), (1,1/3, -1), (-1,1,1), (-1,1, -1/2), (-1,-1,1)]);P1
sage: P1.triangulate()
(<0,1,2,5>, <0,1,5,8>, <0,2,5,8>, <0,2,7,8>, <0,3,7,8>, <1,4,5,8>,
<2,5,7,8>, <3,6,7,8>)
sage: P1.volume()
89/18

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/aeeb5231-fa14-4c14-bc9b-faadf3e43475n%40googlegroups.com.

[Dima Pasechnik]

Following this post, an entertaining discussion of ways to improve
handling of polytopes over RDF has started on
https://trac.sagemath.org/ticket/30699

On Fri, Oct 2, 2020 at 1:26 PM Günter Rote <roteg...@gmail.com> wrote:
>