#10777: Implement CombinatorialPolyhedron
---------------------------+------------------------------------------------
Reporter: novoselt | Owner: mhampton
Type: enhancement | Status: new
Priority: major | Milestone:
Component: geometry | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------+------------------------------------------------
Description changed by novoselt:
Old description:
> While thinking about uniformizing lattice polytopes and cones/fans, I
> came to the conclusion that it would be nice to abstract the current
> "face lattice relations" of cones to a separate class, say
> `CombinatorialPolyhedron`, and include it as a base class for cones,
> lattice polytopes, and polyhedra.
>
> Current situation with faces is "very different":
> * faces of cones are cones, represented by the same class;
> * faces of lattice polytopes are objects of a different class with
> different behaviour of methods with the same name, e.g. for polytopes
> `points` returns a matrix, for their faces - a list of some indices;
> * faces of polyhedra are also objects of some special class.
> I think that ideally all faces of `X` must be represented by objects of
> the same class as `X`, and some methods can be the same for all of the
> above three situations. It may also work nicely for collections of
> objects (i.e. fans and polyhedral complexes).
>
> So, an object of `CombinatorialPolyhedron`, say `cp` should have the
> following properties:
> 1. `cp` knows its "ambient structure" `A`, which can be either an object
> of the same type, or their collection. E.g. each cone sits either in
> another cone or in a fan. Each polyhedron sits in another polyhedron or a
> polyhedron complex.
> 1. `A` knows how to compute its whole face lattice and `cp` knows how to
> access it and use it to create the face lattice of `cp`. This is good for
> efficiency as well as convenience and face walks:
> 1. `cp` can return `facets`, `facet_of`, and `adjacent` elements of the
> face lattice of `A` relative to `cp`.
> 1. Since it may happen that `cp` IS `A`, `cp` should know how to compute
> its face lattice. `Hasse_diagram_from_incidences` computes it quite
> efficiently if incidences of vertex-to-facet and facet-to-vertex are
> known, so perhaps derived classes should provide this information in a
> uniform way and then the actual computation is done in
> `CombinatorialPolytope`. Or maybe it would be more convenient to do it in
> each derived class separately.
>
> It kind of seems that I just want to inherit polyhedra objects from a
> poset element class, but I don't think it will work: I am definitely
> against creating the whole face lattice with all its elements when a
> single polyhedron is created, which is required for using current `Poset`
> function. But then what should be the parent of these elements? On the
> other hand, if it was possible to construct a poset without specifying
> all elements but only providing a way to compare elements, it could be
> quite nice!
>
> In principle, one may think about unifying all polyhedra classes into a
> single one, but I don't think that it is a good idea from the efficiency
> point of view. I think that in general the current separation with
> imposed restrictions is quite reasonable and convenient, especially if
> one can easily switch from one representation to another:
> * cones are always centered at the origin and thought of as fan elements
> or their dual, they are represented by some lattice points;
> * lattice polytopes are bounded and thought of as related to toric
> geometry as well and are represented by lattice points;
> * polyhedra allow complete generality: no binding to any underlying
> lattice, working with inexact fields, maybe even strict inequalities once
> Volker's PPL package is in.
New description:
While thinking about uniformizing lattice polytopes and cones/fans, I came
to the conclusion that it would be nice to abstract the current "face
lattice relations" of cones to a separate class, say
`CombinatorialPolyhedron`, and include it as a base class for cones,
lattice polytopes, and polyhedra.
Current situation with faces is "very different":
* faces of cones are cones, represented by the same class;
* faces of lattice polytopes are objects of a different class with
different behaviour of methods with the same name, e.g. for polytopes
`points` returns a matrix, for their faces - a list of some indices;
* faces of polyhedra are also objects of some special class.
I think that ideally all faces of `X` must be represented by objects of
the same class as `X`, and some methods can be the same for all of the
above three situations. It may also work nicely for collections of objects
(i.e. fans and polyhedral complexes).
So, an object of `CombinatorialPolyhedron`, say `cp` should have the
following properties:
1. `cp` knows its "ambient structure" `A`, which can be either an object
of the same type, or their collection. E.g. each cone sits either in
another cone or in a fan. Each polyhedron sits in another polyhedron or a
polyhedron complex.
1. `A` knows how to compute its whole face lattice and `cp` knows how to
access it and use it to create the face lattice of `cp`. This is good for
efficiency as well as convenience and face walks:
1. `cp` can return `facets`, `facet_of`, and `adjacent` elements of the
face lattice of `A` relative to `cp`.
1. Since it may happen that `cp` IS `A`, `cp` should know how to compute
its face lattice. `Hasse_diagram_from_incidences` computes it quite
efficiently if incidences of vertex-to-facet and facet-to-vertex are
known, so perhaps derived classes should provide this information in a
uniform way and then the actual computation is done in
`CombinatorialPolytope`. Or maybe it would be more convenient to do it in
each derived class separately.
It kind of seems that I just want to inherit polyhedra objects from a
poset element class, but I don't think it will work: I am definitely
against creating the whole face lattice with all its elements when a
single polyhedron is created, which is required for using current `Poset`
function. But then what should be the parent of these elements? On the
other hand, if it was possible to construct a poset without specifying all
elements but only providing a way to compare elements, it could be quite
nice! (See #10783.)
In principle, one may think about unifying all polyhedra classes into a
single one, but I don't think that it is a good idea from the efficiency
point of view. I think that in general the current separation with imposed
restrictions is quite reasonable and convenient, especially if one can
easily switch from one representation to another:
* cones are always centered at the origin and thought of as fan elements
or their dual, they are represented by some lattice points;
* lattice polytopes are bounded and thought of as related to toric
geometry as well and are represented by lattice points;
* polyhedra allow complete generality: no binding to any underlying
lattice, working with inexact fields, maybe even strict inequalities once
Volker's PPL package is in.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10777#comment:2>
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.
