Opened 3 years ago

Closed 2 years ago

# Bug in Voronoi Diagram

Reported by: Owned by: jipilab major sage-9.1 geometry cdd, incidence matrix jipilab, gh-LaisRast Jonathan Kliem Jean-Philippe Labbé N/A fb2d66a fb2d66a0e71f164e9bef37922c8d544b9b270c9c

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:

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}
```

### comment:1 Changed 2 years ago by 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.

### comment:2 Changed 2 years ago by gh-kliem

• Authors set to Jonathan Kliem
• Branch set to public/29176
• Cc jipilab gh-LaisRast added
• Commit set to 33b59112324e37dcbdab7706047e47cf9dbf5568
• Description modified (diff)
• Keywords cdd incidence matrix added
• Status changed from new to needs_review

New commits:

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

### comment:3 Changed 2 years ago by jipilab

• Reviewers set to Jean-Philippe Labbé
• Status changed from needs_review to positive_review

Thanks! Looks good to me.

Thank you.

### comment:5 Changed 2 years ago by vbraun

• Status changed from positive_review to needs_work

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:
```

### comment:6 Changed 2 years ago by git

• Commit changed from 33b59112324e37dcbdab7706047e47cf9dbf5568 to 9352525b50851921f000335615e75e0f1bdd5f2e

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

 ​9352525 `fixed dictionary in python2`

### comment:7 Changed 2 years ago by gh-kliem

• Status changed from needs_work to needs_review

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.

### comment:8 Changed 2 years ago by jipilab

• Status changed from needs_review to positive_review

Thanks for the quick fix.

### comment:9 Changed 2 years ago by vbraun

• Branch changed from public/29176 to 9352525b50851921f000335615e75e0f1bdd5f2e
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:10 Changed 2 years ago by vbraun

• Commit 9352525b50851921f000335615e75e0f1bdd5f2e deleted
• Resolution fixed deleted
• Status changed from closed to new
```**********************************************************************
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]
**********************************************************************
```

### comment:11 Changed 2 years ago by gh-kliem

• Branch changed from 9352525b50851921f000335615e75e0f1bdd5f2e to public/29176-reb
• Commit set to fb2d66a0e71f164e9bef37922c8d544b9b270c9c
• Status changed from new to needs_review

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`

### comment:12 Changed 2 years ago by jipilab

• Status changed from needs_review to positive_review

Thank you.

### comment:14 Changed 2 years ago by vbraun

• Branch changed from public/29176-reb to fb2d66a0e71f164e9bef37922c8d544b9b270c9c
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.