Algorithms for frames and lineality spaces of cones

A fram e of a co ne C is a minimal se t of generators, and the lin eaJity space L of C is th e grea tes t lin ea r s ubs pace co ntain ed in C. Algorithm s are desc ribed for determinin g a fram e and th e lin ea lit y sp ace of a c one C(S) s panned by a finit e se t S . Th ese a lgorit hm s ca n be used for determ inin g th e ve rti ces, ed ges, and oth e r fa ces of low dim e ns ion of th e co nv ex hull of a finit e set H (S) . All algo rit hill s are based on th e s impl ex me th od of lin ea r programm in g. Th e problem of findin g th e lin ea lit y s pac e ca n be success ive ly redu ced to prob le ms in s paces of lowe r dim e ns ions.