Construct RationalPolyhedralFan from possibly overlapping cones

[yzh]

Given a cone arrangement where the cones are not necessarily face-to-face, construct a rational polyhedral fan that is a subdivision of the cone arrangement. This could be useful for topological computations with non-convex unions of polyhedral sets.

In the following example, the intersection of the cones c1 and c2 is not a face of each. Thus, they do not belong to the same rational polyhedral fan. By using the allow_arrangement=True option in the Fan constructor, we construct a fan so that c1 and c2 are unions of cones in the fan. There is no guarantee that it will be "the" coarsest subdivision, though.

sage: c1 = Cone([(-2,-1,1), (-2,1,1), (2,1,1), (2,-1,1)])
sage: c2 = Cone([(-1,-2,1), (-1,2,1), (1,2,1), (1,-2,1)])
sage: Fan([c1,c2])
Traceback (most recent call last):
...
ValueError: these cones cannot belong to the same fan!
...
sage: fan = Fan([c1, c2], allow_arrangement=True)
sage: fan.ngenerating_cones()
5
sage: fan.plot()
Graphics3d Object

[novoselt]

What the result should be? The coarsest subdivision? And in what situations is it necessary?

[yzh]

New commits:

​984ba24

implement allow_arrangement option in Fan constructor

[moritz]

Please put your name as an author, yzh

[mkoeppe]

allow_arrangement is misspelled once in the documentation

[git]

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

​4371ee7

fix a typo in documentation

[mkoeppe]

Moving some tickets to 9.2. This is not a promise that I will be working on them.

[mkoeppe]

**********************************************************************
File "src/sage/geometry/fan.py", line 510, in sage.geometry.fan.?
Failed example:
    for cone in fan.generating_cones(): print(cone.rays())
Expected:
    N(1, 0),
    N(2, 1)
    in 2-d lattice N
    N(1, 2),
    N(2, 1)
    in 2-d lattice N
    N(1, 2),
    N(0, 1)
    in 2-d lattice N
    N(-1, -2)
    in 2-d lattice N
Got:
    N(2, 1),
    N(1, 0)
    in 2-d lattice N
    N(1, 2),
    N(2, 1)
    in 2-d lattice N
    N(1, 2),
    N(0, 1)
    in 2-d lattice N
    N(-1, -2)
    in 2-d lattice N
**********************************************************************

This doctest should be rewritten so it does not depend on the unspecified orders of cones in the fan and rays in the cones.

[mkoeppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

Rebased on 9.3.beta6

---

New commits:

​dd32a12

implement allow_arrangement option in Fan constructor

[git]

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

​2018fda

src/sage/geometry/fan.py: Make a doctest more stable by using 'sorted'

[mkoeppe]

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review.

[vbraun]

**********************************************************************
File "src/sage/geometry/fan.py", line 512, in sage.geometry.fan.?
Failed example:
    for cone in sorted(fan.generating_cones()): print(sorted(cone.rays()))
Expected:
    N(1, 0),
    N(2, 1)
    in 2-d lattice N
    N(1, 2),
    N(2, 1)
    in 2-d lattice N
    N(0, 1),
    N(1, 2)
    in 2-d lattice N
    N(-1, -2)
    in 2-d lattice N
Got:
    [N(-1, -2)]
    [N(0, 1), N(1, 2)]
    [N(1, 0), N(2, 1)]
    [N(1, 2), N(2, 1)]
**********************************************************************
1 item had failures:
   1 of  52 in sage.geometry.fan.?
    [523 tests, 1 failure, 3.67 s]
----------------------------------------------------------------------
sage -t --long --warn-long 43.7 --random-seed=0 src/sage/geometry/fan.py  # 1 doctest failed
----------------------------------------------------------------------

[yzh]

New commits:

​7a4d5fa

fix doctest bug introduced in commit 2018fda regarding sorted

[git]

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

​6bea882

make tox happy: Returns changed to Return