id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
29176,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}
}}}",defect,closed,major,sage-9.1,geometry,fixed,"cdd, incidence matrix",jipilab gh-LaisRast,,Jonathan Kliem,Jean-Philippe Labbé,N/A,,fb2d66a0e71f164e9bef37922c8d544b9b270c9c,fb2d66a0e71f164e9bef37922c8d544b9b270c9c,,