Bug in Voronoi Diagram

[jipilab]

We fix a bug that was exposed computing an inexact Voronoi Diagram (see below).

cdd already computes the incidence matrix, we expose it in this ticket.

When deciding whether or not a vertex lies on a hyperplane for inexact polyhedra, we allow numerical noise up to absolute value of 1e-6. This might be a bad choice depending on the size of the polyhedron as witnessed in the following example:

sage: e = [[11582947.657000002, 5374.38, 4177.06, 1.0], [11562795.9322, 5373.62, 4168.38, 1.0]]
sage: p = Polyhedron(ieqs=e); p
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line
sage: p.incidence_matrix()
[0 0]
[0 0]
[0 1]
[0 0]

Setting the cache of incidence matrix to the matrix that cdd already computed for us produces the correct output:

sage: p.incidence_matrix()
[1 1]
[1 0]
[0 1]
[1 1]

This fixes the error reported here:

​https://ask.sagemath.org/question/49749/voronoidiagram-returns-empty-regions/

The following should give two non-empty regions

sage: P = [[-2687.19, -2088.53], [-2686.81, -2084.19]]
....: V = VoronoiDiagram(P)
....: R = V.regions()
....: 
sage: R
{P(-2687.19000000000, -2088.53000000000): The empty polyhedron in RDF^0,
 P(-2686.81000000000, -2084.19000000000): A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex and 1 ray

With this ticket we obtain:

sage: R
{P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line,
 P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}

[gh-kliem]

This can and should be solved by fetching the incidences from cdd.

I will try to do so. This might get rid of a lot of numerical inconsistencies.

[gh-kliem]

New commits:

​c03aee4	expose incidence matrix computed by backend cdd
​33b5911	add doctests that 29176 is fixed

[jipilab]

Thanks! Looks good to me.

[gh-kliem]

Thank you.

[vbraun]

On Python 2 Debian 9 x86_64:

**********************************************************************
File "src/sage/geometry/polyhedron/backend_cdd.py", line 231, in sage.geometry.polyhedron.backend_cdd.Polyhedron_cdd._init_from_cdd_output
Failed example:
    R
Expected:
    {P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line,
     P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}
Got:
    {P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line,
     P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}
**********************************************************************
1 item had failures:

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9352525

fixed dictionary in python2

[gh-kliem]

I tested this in python2:

>>> {(-2686.81000000000, -2084.19000000000): 0, (-2687.19000000000, -2088.53000000000): 0}
{(-2687.19, -2088.53): 0, (-2686.81, -2084.19): 0}

So the fix should work fine.

[jipilab]

Thanks for the quick fix.

[vbraun]

**********************************************************************
File "src/sage/geometry/polyhedron/backend_cdd.py", line 234, in sage.geometry.polyhedron.backend_cdd.Polyhedron_cdd._init_from_cdd_output
Failed example:
    R  # py2
Expected:
    {P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line,
     P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}
Got:
    {P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line,
     P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}
**********************************************************************
1 item had failures:
   1 of  10 in sage.geometry.polyhedron.backend_cdd.Polyhedron_cdd._init_from_cdd_output
    [46 tests, 1 failure, 0.59 s]
**********************************************************************

[gh-kliem]

Got rid of the dictionary printing in the tests.

---

New commits:

​2860b02	expose incidence matrix computed by backend cdd
​b13fb31	add doctests that 29176 is fixed
​581f554	fixed dictionary in python2
​fb2d66a	fix test by avoiding printing the dictionary at all

[gh-kliem]

Thank you.