hyperplane arrangements raises error on regions

[Murad Tukan]

Dear all,

Computer info:

CPU: i7-6500U @ 2.50GHZ

Memory: 16.0GB

Sage information: SageMath 9.0 (Windows, installed using the .exe file), and even on Linux version.

Platforms ran at: SageMath 9.0 Shell, SageMath 9.0 Notebook, From Python script (and then running the command sage -python "script_name.py").

Description of problem:

When running the following code:

P = [[-0.48,  0.83], [-5.33,  9.23]]

Q = [[0.43, 0.        ], [9.04, 0.        ]]

Z =  [[-0.35, -0.60], [-1.44, -2.49]]

V = VoronoiDiagram(P)

R = [r for r in V.regions().items()]

s = R[0][1].hyperplane_arrangement()

V = VoronoiDiagram(Q)

R = [r for r in V.regions().items()]

s = s.add_hyperplane(R[0][1].hyperplane_arrangement())

V = VoronoiDiagram(Z)

R = [r for r in V.regions().items()]

s = s.add_hyperplane(R[0][1].hyperplane_arrangement())

s.regions()

Sage fails to compute the regions which is weird since it can compute the vertices which means that there is even a bounded region (in my case). When running the same code on SageMathCell, It is computed smoothly while on my machine it is not!

The full traceback I get is:

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

<ipython-input-6-4ba993d8025f> in <module>()

----> 1 s.regions()

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:12712)()

   2308         if self.cache is None:

   2309             f = self.f

-> 2310             self.cache = f(self._instance)

   2311         return self.cache

   2312

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/hyperplane_arrangement/arrangement.py in regions(self)

   1608         R = self.base_ring()

   1609         dim = self.dimension()

-> 1610         universe = Polyhedron(eqns=[[0] + [0] * dim], base_ring=R)

   1611         regions = [universe]

   1612         for hyperplane in self:

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/constructor.py in Polyhedron(vertices, rays, lines, ieqs, eqns, ambient_dim, base_ring, minimize, verbose, backend)

    660     if got_Vrep:

    661         Vrep = [vertices, rays, lines]

--> 662     return parent(Vrep, Hrep, convert=convert, verbose=verbose)

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9245)()

    900                 return mor._call_(x)

    901             else:

--> 902                 return mor._call_with_args(x, args, kwds)

    903

    904         raise TypeError(_LazyString(_lazy_format, ("No conversion defined from %s to %s", R, self), {}))

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:5081)()

    178                 print(type(C), C)

    179                 print(type(C._element_constructor), C._element_constructor)

--> 180             raise

    181

    182

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:4969)()

    173                     return C._element_constructor(x, *args)

    174                 else:

--> 175                     return C._element_constructor(x, *args, **kwds)

    176         except Exception:

    177             if print_warnings:

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/parent.py in _element_constructor_(self, *args, **kwds)

    523             if convert and Vrep:

    524                 Vrep = [convert_base_ring(_) for _ in Vrep]

--> 525             return self.element_class(self, Vrep, Hrep, **kwds)

    526         if nargs == 1 and is_Polyhedron(args[0]):

    527             polyhedron = args[0]

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in __init__(self, parent, Vrep, Hrep, **kwds)

    459             sage: TestSuite(p).run()

    460         """

--> 461         Polyhedron_cdd.__init__(self, parent, Vrep, Hrep, **kwds)

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in __init__(self, parent, Vrep, Hrep, **kwds)

    125         elif Hrep is not None:

    126             ieqs, eqns = Hrep

--> 127             self._init_from_Hrepresentation(ieqs, eqns, **kwds)

    128         else:

    129             self._init_empty_polyhedron()

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in _init_from_Hrepresentation(self, ieqs, eqns, verbose)

    114         s = cdd_Hrepresentation(self._cdd_type, ieqs, eqns)

    115         s = self._run_cdd(s, '--redcheck', verbose=verbose)

--> 116         s = self._run_cdd(s, '--repall', verbose=verbose)

    117         self._init_from_cdd_output(s)

    118         if not self.base_ring().is_exact():

/opt/sagemath-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in _run_cdd(self, cdd_input_string, cmdline_arg, verbose)

    163         if 'Error:' in ans + err:

    164             # cdd reports errors on stdout and misc information on stderr

--> 165             raise ValueError(ans.strip())

    166         return ans

    167

ValueError: *Input Error: Input format is not correct.

*Format:

 begin

   m   n  NumberType(real, rational or integer)

   b  -A

 end

How can i fix this problem!?

[Matthias Koeppe]

Try if it works if you use rationals (-48/100) instead of floats (-0.48).

[Murad Tukan]

This actually works fine. Why when running with 2 digit floating points, the code doesn't run? Is there any way to make it work with floats??

[Dima Pasechnik]

On Mon, Feb 3, 2020 at 2:49 PM Murad Tukan <mura...@gmail.com> wrote:
>
> This actually works fine. Why when running with 2 digit floating points, the code doesn't run? Is there any way to make it work with floats??

it's not documented properly, but looking at the source (e.g. by doing
VoronoiDiagram??)
tells you that
raise NotImplementedError('Base ring of the Voronoi diagram must '
'be one of QQ, RDF, AA.')

Thus if Sage encounters floating point input there, it uses RDF (Real
Double Float, i.e. the usual x86_64 double).
This is not very robust. I guess the algorithm in Sage is a native one.

You might try scipy's
https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.spatial.Voronoi.html
perhaps it's more efficient if you must use floats.

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/c77ba5f3-c32a-459d-9258-adccbee38ec2%40googlegroups.com.