Changes between Initial Version and Version 2 of Ticket #29176


Ignore:
Timestamp:
03/19/20 14:55:32 (19 months ago)
Author:
gh-kliem
Comment:

New commits:

c03aee4expose incidence matrix computed by backend cdd
33b5911add doctests that 29176 is fixed

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #29176

    • Property Status changed from new to needs_review
    • Property Authors changed from to Jonathan Kliem
    • Property Cc jipilab gh-LaisRast added
    • Property Branch changed from to public/29176
    • Property Keywords cdd incidence matrix added
    • Property Commit changed from to 33b59112324e37dcbdab7706047e47cf9dbf5568
  • Ticket #29176 – Description

    initial v2  
    1 The following should give two non-empty regions:
     1We fix a bug that was exposed computing an inexact Voronoi Diagram (see below).
     2
     3`cdd` already computes the incidence matrix, we expose it in this ticket.
     4
     5When 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:
     6
     7{{{
     8
     9sage: e = [[11582947.657000002, 5374.38, 4177.06, 1.0], [11562795.9322, 5373.62, 4168.38, 1.0]]
     10sage: p = Polyhedron(ieqs=e); p
     11A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 2 rays, 1 line
     12sage: p.incidence_matrix()
     13[0 0]
     14[0 0]
     15[0 1]
     16[0 0]
     17}}}
     18
     19Setting the cache of incidence matrix to the matrix that `cdd` already computed for us produces the correct output:
     20
     21{{{
     22sage: p.incidence_matrix()
     23[1 1]
     24[1 0]
     25[0 1]
     26[1 1]
     27}}}
     28
     29This fixes the error reported here:
     30
     31https://ask.sagemath.org/question/49749/voronoidiagram-returns-empty-regions/
     32
     33The following should give two non-empty regions
    234
    335{{{
     
    1143}}}
    1244
    13 This way reported here:
     45With this ticket we obtain:
    1446
    15 https://ask.sagemath.org/question/49749/voronoidiagram-returns-empty-regions/
     47{{{
     48sage: R
     49{P(-2687.19000000000, -2088.53000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line,
     50 P(-2686.81000000000, -2084.19000000000): A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex, 1 ray, 1 line}
     51}}}