Construct RationalPolyhedralFan from possibly overlapping cones

[yuan-zhou]

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

CC: @novoselt @vbraun @mo271 @jplab @mkoeppe

Component: geometry

Keywords: RationalPolyhedralFan, cone arrangement, IMA-PolyGeom

Author: Yuan Zhou

Branch/Commit: 6bea882

Reviewer: Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/25122

[novoselt]

comment:1

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

[yuan-zhou]

Description changed:

--- 
+++ 
@@ -1 +1,20 @@
+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
+```
+

[yuan-zhou]

Changed keywords from none to RationalPolyhedralFan, cone arrangement, IMA-PolyGeom

[yuan-zhou]

Branch: u/yzh/construct_rationalpolyhedralfan_from_possibly_overlapping_cones

[yuan-zhou]

Commit: 984ba24

[yuan-zhou]

New commits:

984ba24

implement allow_arrangement option in Fan constructor

[mo271]

comment:5

Please put your name as an author, yzh

[yuan-zhou]

Author: Yuan Zhou

[mkoeppe]

comment:7

allow_arrangement is misspelled once in the documentation

[sagetrac-git]

Changed commit from 984ba24 to 4371ee7