#7109: polyhedra bugs with linearities, rewrite proposal
-------------------------+--------------------------------------------------
Reporter: vbraun | Owner: mhampton
Type: enhancement | Status: new
Priority: major | Milestone: sage-feature
Component: geometry | Keywords: polyhedra
Reviewer: | Author:
Merged: |
-------------------------+--------------------------------------------------
The Polyhedron class is an interface to cdd, but does not correctly map
some of the features that go beyond compact, full-dimensional polyhedra.
For starters, "linearities" means two different things for H- and
V-representation (equalities or lines), but there is only one
self.linearities() method. For reference:
'''H-representation: inequalities and equalities'''
'''V-representation: conv(vertices) + IR_+{rays} + IR{lines}'''
It is often confusing what has already been computed from the
complementary representation and what has not been computed, and the
package does not always get it right. For example:
{{{
sage: vert_to_ieq(vertices=[[0]], rays=[[1]]).linearities()
[[0, 1]]
sage: Polyhedron(vertices=[[0]], rays=[[1]]).linearities()
[]
}}}
Also, the constructor by default eliminates redundant vertices but not
other redundant data which can be confusing.
Finally, ccd pivots and hence changes the enumeration of the data. This
makes parsing the incidences and adjacencies tricky.
=== Proposal ===
I propose to change the behaviour of Polyhedron such that the constructor
automatically computes both an optimized H-representation and an optimized
V-representation. Thereafter, no more calls to cdd would be necessary.
If one really wants to use Polyhedron as a container for only
H-representation or only V-representation, then a special class
constructing function can do that. Any calls to methods that require the
complementary data shall then fail with an {{{AttributeError}}} exception.
=== cdd caveats ===
cdd sometimes omits the origin as a vertex:
{{{
sage: Polyhedron(ieqs=[[0, 1]]).vertices()
[]
}}}
cdd also sometimes adds a "inequality at infininty"; Contrary to the
output below, the half-line has only one face
{{{
sage: Polyhedron(vertices=[[0]], rays=[[1]]).facial_incidences()
[[0, [0]], [1, [1]]]
}}}
Given equations/inequalities without a solution, cdd will return an empty
polyhedron (no vertices). But conversely, given an empty polyhedron, cdd
will error out instead of producing equations without solution (one of the
cases where the H-representation is not unique)
=== Plan ===
1) Write a binary based on cddlib that acts as a filter stdin->stdout and
computes an canonical H- and V-representation. I'll attach a suitable
patch against the contents of cddlib-094f.spkg
2) change polyhedra.py to run cdd only once in the constructor (TODO)
3) compute incidence matrix within sage as cddlib does not have a
convenient function to do so without adding an "inequality at infinity"
(TODO)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7109>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
