lrs is based on the reverse
search algorithm developed with Komei Fukuda, see (AF1992)
, modified to use lexicographic pivoting and implemented in
rational arithmetic. It uses limited multithreading via OpenMP. (Av1998a)
contains a technical description, and (Av1998b)
contains some computational experience.
mplrs is a full parallel
version of lrs based on Open
MPI for distributed systems, developed with Skip Jordan, see (AJ2015).
The input files are in Polyhedra format , developed with
Fukuda. The format is essentially selfdual, and the output file
produced can be read in as an input file, with very minor
modifications, to perform the reverse transformation. This format
is compatible with that used in Fukuda's
cddlib package, which performs the same
transformations using a version of the double description
method. The program normaliz
provides a parallel version of the double description method.
Another program using the same file format is the primaldual
method pd,
developed by Bremner, Fukuda and Marzetta . It is
essentially dual to lrs, and
is very efficient for computing Hrepresentations of simple
polyhedra, and Vrepresentations of simplicial polyhedra. It will
compute the volume of a polytope given by an Hrepresentation.
Links to additional VE/CH programs are given here.
Polyhedra handled by lrs need not be full
dimensional and may contain input linearities and redundant
columns . lrs accepts either integer or rational
input, and produces integer or rational output. All computations
are done exactly using hybrid arithmetic, starting with 64 bits
and moving to 128 bits and extended precision (GMP or builtin) if
necessary, see (AJ2021).
Since it is a pivot based method, lrs can be very slow for
degenerate inputs: i.e. Hrepresentations of nonsimple polyhedra,
and Vrepresentations of nonsimplicial polyhedra. On the other
hand, it does not store the vertices/ rays or facets produced, so
for very large problems it may be the only method that can solve
the problem. Using mplrs, even with just a few cores,
significantly speeds up the computation. A discussion of various
vertex enumeration/convex hull methods and the types of polyhedra
that cause them to behave badly is contained in (ABS
1997). A more recent discussion with extensive empiral
tests can be found in (AJ2017).
Considerable technical assistance over several decades has been
provided by David Bremner.
Functions of mplrs/lrs include:
These programs can be distributed freely under the GNU GENERAL PUBLIC LICENSE. Please read the file COPYING carefully before using. Please inform the authors of any interesting applications for which these programs were helpful.
{list of inequalities }
end
{options}
name is a user supplied name for the
polytope. If the line Hrepresentation is omitted,
Hrepresentation is assumed. The input coefficients are
read in free format, and are not checked for type. Coefficients
are separated by white space. Normally this file would be saved
with filename suffix .ine but this not required.
Comments may appear before the begin or after the end, and to
avoid interpretation as an option, should begin with a special
character such as "*" or "#".
The integer m is the number of inequalities, and the
integer n is the dimension of the input +1.
A list of inequalities contains the coefficients of inequalities
of the form
a_{0} + a_{1 }x_{1 }+ ... + a_{n1} x_{n1} >= 0.
This inequality is input as the line
a_{0 }a_{1 }... a_{n1}
The coefficients can be entered as integers or rationals in the
format x/y.
For example, the square centred at the origin with side length
two has inequalities
1 + x_{1} >= 0 1+ x_{2 }>=0 1x_{ 1 }>= 0 1x_{2 }>=0
and would be represented by the input file
square
*centred square of side 2
Hrepresentation
begin
4 3 rational
1 1 0
1 0 1
1 1 0
1 0 1
end
{list of vertices and extreme rays}
end
{options)
The integer m is the number of vertices and rays,
and the integer n is the dimension of the input +1.
Each vertex is given in the form
1 v_{0 } v _{1 }...
v_{n1}
Each ray is given in the form
0 r_{0 } r _{1 }... r_{n1}
where r_{0 } r _{1 }... r_{ n1}is a point on the ray.
There must be at least one vertex in each file. For bounded
polyhedra there will be no rays entered.
The coefficients can be entered as integers or rationals in the
format x/y.
For example, the unit square centred at the origin has vertices
(1,1) ,(1,1),(1,1),(1,1)
and would be represented by the input file
square
*centred square of side 2
Vrepresentation
begin
4 3 rational
1 1 1
1 1 1
1 1 1
1 1 1
end
The positive quadrant has vertex (0,0) and rays (1,0) (0,1) and is represented
quadrant
*positive quadrant
Vrepresentation
begin
3 3 rational
1 0 0
0 1 0
0 0 1
end
Its Hrepresentation contains the inequalities x_{1 }>= 0 and x_{2} >= 0 :
quadrant
*positive quadrant
Hrepresentation
begin
2 3 rational
0 1 0
0 0 1
end
Print out cryptic but detailed trace, dictionaries etc. starting at #B=startingbasis and ending at #B=endingbasis. debug 0 0 gives a complete trace.digits n // placed before the begin statement//
Can be used with printcobasis n. (Ver 4.2b)#incidenceFor input Hrepresentation, indices of all input inequalities that contain the vertex/ray that is about to be output. For a simplicial face, there is no new output, since these indices are already listed. Otherwise, the additional tight inequalities are listed after a colon. Eg:
V#1 R#0 B#1 h=0 facets 12 14 15 16 : 9 10 11 13 I#8 det= 8
1 0 0 0 1
The vertex 0 0 0 1 satisfies 8 input inequalities as equations, as indicated by I#8 : those with indices 12,14,15,16 are in the cobasis, and those with indices 9, 10, 11, 13 are in the basis. For a ray:
V#1 R#5 B#1 h=0 facets 5 9* 10 11 12 13 : 2 3 4 I#8 det= 8
0 1 1 0 0 1 1
Here the ray 1 1 0 0 1 1 lies on 8 inequalities, with indices 5 10 11 12 13 in basis and 2 3 4 in cobasis. The starred index 9* indicates that the ray is terminated by the input inequality 9. This inequality is in the cobasis and defines the vertex from which the ray starts.For input Vrepresentation, indices of all input vertices/rays that lie on the facet that is about to be output:
F#5 B#3 h=2 vertices/rays 7 8* 11 13 15 : 1 3 5 9 I#8 det= 16
1 1 0 0 0
The facet generated by inequality x_{1} <= 1 contains 8 input vertices, as indicated by I#8: those with indices 7,11,13,15 are in the cobasis, and those with indices 1 3 5 9 are in the basis.The starred index 8* indicates that this vertex is also in the cobasis, but is not contained in the facet. It arises due to the lifting operation used with input Vrepresentations.
The same as printcobasis. Included for compatability with cdd.linearity k i_{1 }i_{2 } i ... i_{k}
The input contains k linearities in rows i_{1 }i_{2 }i ... i_{k }of the input file are equations. See Linearities.maxdepth k
For problems where the input is an Hrepresentation of the form b+Ax>=0, x>=0 (ie. all variables nonnegative, all constraints inequalities) it is not necessary to give the nonnegative constraints explicitly if the nonnegative option is used. This option cannot be used for Vrepresentations, or with the linearity option (in which case the linearities will be treated as inequalities). This option may be used with redund , but the implied nonnegativity constraints are not tested themselves for redundancy. To test everything it is necessary to enter the nonnegativity constraints explicitly in the input file. (In Ver 4.1, the origin must be a vertex).
printcobasis k
F#5 B#4 h=3 vertices/rays 2 3
4 5* det= 8
1 0 0 1
enter
restart 5 4 3 2 3 4 5
Note that if some cobasic index is
followed by a "*", then the index only, without the
"*", is included in the restart line.
Caution:
When restarting, output
from the restart dictionary may be duplicated, and the final
totals of number of vertices/rays/facets may reflect this.
The reverse search tree is truncated(pruned) whenever a new vertex is encountered. Note: This does note necessarily produce the set of all vertices adjacent to the optimum vertex in the polyhedron, but just a subset of them. See here for a description of how to use this option.verbose
Print slightly more detailed information about the run.volume // Vrepresentation only //
lrslong
Fixed length long integer arithmetic. 64bit and 128bit(when
the compiler supports it) with overflow
checking
lrsgmp An
interface to GNU MP which must be installed first from https://gmplib.org/.
produces the binaries :
lrs1/lrsnash1
fixed 64 bit, stop on
overflow
lrs2/lrsnash2
fixed 128 bit, stop on overflow
lrsgmp/lrsnashgmp
gmp extended precison arithmetic
and if the FLINT package has been installed ( available at http://www.flintlib.org/
)
lrsflint
FLINT multiple precison arithmetic
lrs1/lrs2 produce a
restart file that can be used instead of redoing the whole
run from the beginning
If you remove the flag DSAFE in the
makefile then (mp)lrs1 and (mp)lrs2 will not do overflow
checking and will run about 10% faster.
However, if overflow occurs the results are unpredictable:
caveat emptor!
% make singlemplrs produces the binaries :
mplrs1
64 bit integers with overflow checking. Terminates when
overflow condition is detected.
mplrs2 128 bit integers with overflow
checking. Terminates when overflow condition is detected.
mplrsgmp(default mplrs) use only gmp extended
precison arithmetic (same as lrs in lrslib062)
lrslib also has support for the
multiprecision FLINT package that needs to be installed from http://www.flintlib.org/
% make flint produces the binary lrsflint
% make mplrsflint produces the binary mplrsflint
(mp)lrs1 runs 35 times faster than
(mp)lrs on highly combinatorial polytopes.
(mp)lrsflint performed similarly to (mp)lrsgmp even on
combinatorial polytopes.
Experimental results will be reported at a later date.
Examples
% lrs mp5.ine mp5.ext
*lrs:lrslib v.6.3 2018.4.11(64bit,lrsmp.h)
*Input taken from file mp5.ine
*Output sent to file mp5.ext
*Totals: vertices=32 rays=0 bases=9041 integer_vertices=16
*Dictionary Cache: max size= 17 misses= 0/9040 Tree Depth= 16
In this case 64 bit arithmetic was
sufficient to compute all vertices.
% lrs mit.ine mit.extIn this case 64bit arithmetic triggered an overflow condition so 128bit lrs2 was used with a restart.
*lrs:lrslib v.7.0 2018.5.1(64bit,lrslong.h,overflow checking)
*Input taken from file mit.ine
*Output sent to file mit.ext
*overflow possible: restarting with longer precision arithmetic from /tmp/lrs_mit.ine_restart
*lrs:lrslib v.7.0 2018.5.1(128bit,lrslong.h,overflow checking)
*Input taken from file /tmp/lrs_mit.ine_restart
*Output sent to file mit.ext
*Totals: vertices=4862 rays=0 bases=1375608 integer_vertices=477
*Dictionary Cache: max size= 50 misses= 1053/1374992 Tree Depth= 101
*367.370u 1.819s 9616Kb 0 flts 0 swaps 0 blksin 712 blksout
% lrs c3015.ext c3015.ineIn this case neither 64bit or 128bit precision is enough so lrsgmp was used for the computation.
*lrs:lrslib v.7.0 2018.5.1(64bit,lrslong.h,overflow checking)
*Input taken from file c3015.ext
*Output sent to file c3015.ine
*overflow possible: restarting with longer precision arithmetic from /tmp/lrs_c3015.ext_restart
*lrs:lrslib v.7.0 2018.5.1(128bit,lrslong.h,overflow checking)
*Input taken from file /tmp/lrs_c3015.ext_restart
*Output sent to file c3015.ine
*overflow possible: restarting with longer precision arithmetic from /tmp/lrs_c3015.ext_restart
*lrs:lrslib v.7.0 2018.5.1(64bit,lrsgmp.h) gmp v.6.1
*Input taken from file /tmp/lrs_c3015.ext_restart
*Output sent to file c3015.ine
*Totals: facets=341088 bases=319770
*Dictionary Cache: max size= 15 misses= 0/319769 Tree Depth= 14
*52.359u 1.046s 4320Kb 1125 flts 0 swaps 0 blksin 0 blksout
Hrepresentation: If the input is an
Hrepresentation, the program gives an unbiased estimate of
the number of vertices and rays in the
Vrepresentation, and the total number of bases that
will be computed by lrs. For the Hrepresentation cube.ine,
the options maxdepth 1 and
estimates 1 produce the
output:
*Estimates:
vertices=9 rays=0
bases=9
*Total number of tree nodes
evaluated: 6
*Estimated total running
time=0.0 secs
In this case the Vrepresentation of the cube
is estimated to have 9 vertices, and it is estimated that lrs
will compute a total of 9 bases. The estimate was based on
evaluating 6 tree nodes. Note: The estimate for
the number of rays may be an overestimate if the polyhedron is
not a cone, since some rays may be duplicated in the output 
see subsection Output
Duplication.
Vrepresentation: If the
input is a Vrepresentation, the program gives an unbiased
estimate of the number of facets in the Hrepresentation, and
the total number of bases that lrs will compute.
For Vrepresentation cube.ext, the options maxdepth 0 and estimates 3 produce the
output:
*Estimates: facets=6 bases=7 volume=8.88889
*Total number of tree
nodes evaluated: 10
*Estimated total
running time=0.0 secs
In this cases it is estimated that the Hrepresentation of the
cube will contain 7 facets, and it is estimated that lrs
will compute a total of 7 bases to find it.
An unbiased estimate of the volume of the polytope is also
given. The estimate was formed by evaluating 7 tree
nodes.
Voronoi diagrams: Estimates for the number of Voronoi vertices and Voronoi rays for a Vrepresentation of a set of data points may be obtained by combining the voronoi, estimates and maxdepth options.
Repeated estimates: In order to get estimates with different random probes, lrs can be given a seed for the random number generator by the seed option.
The estimates may also be used to judge the feasibility of solving the problem using other codes. For example, any code that uses triangulation/perturbation to resolve degeneracy will have trouble if the number of bases is huge. Codes which must store all the output in memory (currently all codes except reverse search methods such as lrs) will have trouble if the estimated output size is huge.
lrsnash computes all Nash equilibria (NE) for a two person noncooperative game are computed using two interleaved reverse search vertex enumeration steps.
The input for the problem are two m by n matrices A,B of integers or rationals. The first player is the row player, the second is the column player.
If row i and column j are played, player 1 receives A_{i,j} and player 2 receives B_{i,j}.
and one of the options maximize or minize:
maximize a_{0} a_{1 }... a_{n1} // Hrepresentation only //
To print the dictionary at a few key points also include the option:
verbose
New
in
V4.2. Dual variables are now printed at
termination. If the linearity option is used, only a partial
list of dual variables will be given.
Dual
variable
y_{i} refers to inequality number i in the input.
volume // Vrepresentation only //
will cause the volume to be computed. For input cube.ext, the
output is:
*Volume=8
The triangulation can be output by adding also the option verbose.
This would give the output:
F#0 B#1
h=0 vertices/rays 4 6 7 8 I#8 det= 8
1
1
0 0
1
0
1 0
1
0
0 1
F#3 B#2
h=1 vertices/rays 4 5 6 7 I#8 det= 8
F#3 B#3
h=2 vertices/rays 3 4 5 7 I#8 det= 8
1
1 0 0
F#4 B#4
h=3 vertices/rays 2 3 4 5 I#8 det= 8
1
0
0 1
F#5 B#5
h=4 vertices/rays 1 2 3 5 I#8 det= 8
F#5 B#6
h=2 vertices/rays 2 4 5 6 I#8 det= 8
1
0 1 0
end
*Sum of
det(B)= 48
*Volume=
8
Each of the 6 bases corresponds to a simplex.
The first simplex is composed of vertices 4 6 7 8, second
simplex is 4 5 6 7, etc.
If the volume option is applied to an Hrepresentation, the results are not predictable. If the option is applied to a Vrepresentation of a polytope that is not full dimensional, the volume of a projected polytope is computed. The projection used is to the lexicographically smallest coordinate subspace, see Avis, Fukuda, Picozzi (2002).
For polytopes given by a Hrepresentation, it will first be
necessary to compute the Vrepresentation.
p_{1 } , p_{2 } , ...., p_{ n1} > (p_{1 }^{ 2 }+ p_{2}^{2 }+ ... + p_{n1}^{2 } )  2 p_{1} x_{ 1 }  2 p_{2 } x_{2 } ....  2 p_{ n1 }x_{n 1 } + x _{n}>= 0
lrs is applied to the Hrepresentation so created. This transformation is performed automatically for a Vrepresentation if the
voronoi // Vrepresentation only  place immediately after end statement //
option is specified.
Note: The input file must consist entirely of data points
(no rays), i.e.. there must be a one in column one of each line.
The volume option should
not be used, since the volume reported will not be the volume of
the original Vrepresentation.
The output will consist of the Voronoi vertices (columns
beginning with a one) and Voronoi rays (columns beginning with
zero) for the Voronoi diagram defined on the data points.
If the printcobasis option
is given, the n "data points"
indices produced will tell which set of input data points
corresponds to the given Voronoi vertex or ray. In case of
degeneracies, a given Voronoi vertex may be generated by more
than n of the input data points. In this case, use of the allbases option will cause
all sets of n input data points corresponding to a Voronoi
vertex to be printed. Each cobasis will define a Delaunay triangle in the dual.
For Voronoi rays, the immediately preceding cobasis is the
cobasis of the the Voronoi vertex from which the ray
emanates. The index followed by a * is
the data point to drop in order to generate the ray. If the geometric option is given the
correspondence between Voronoi rays and Voronoi vertices will be
produced automatically.
Example: Compute the
Voronoi diagram and Delaunay triangulation of the planar point
set (0,0), (2,1), (1,2), (0,4), (4,0), (4,4) (2,4).
Input: vor73.ine *6 Voronoi *7 input data pointVrepresentation begin 7 3 integer 1 0 0 1 2 1 1 1 2 1 0 4 1 4 0 1 4 4 1 2 4 end voronoi printcobasis allbases geometric Run: % lrs vor73.ine 
Output: Vrepresentation

Voronoi diagram: Blue circles
mark input data points, Voronoi diagram in black
V#1 R#1 B#1 h=0 data points 1 5* 7 det=64 0 2 1 This means that the ray (2t,t) emanates from the vertex V#1 defined by data points 1 5 7, namely (2, 3/2). The asterisk on index 5 indicates that the ray is defined by the data points with indices 5 and 7, namely (0,0) and (2,4). 
Delaunay triangulation Blue circles mark input data points, Delaunay triangulation in red. Each of the 7 cobases defines a triangle in the dual: 157, 125, 123, 134, 256, 236, 346 Here each index refers to the line number of the data point in the input file. Eg. 157 describes the triangle (0,0),(4,0),(2,4) 
Visualizations made using GeoGebra.
To remove input lines that are not vertices/rays from a Vrepresentation or redundant inequalities from an Hrepresentation use the command:
*redund:lrslib v.7.1 2020.5.23(64bit,lrslong.h,overflow checking)From this output we first see that redund tried 64 bit arithmetic but detected an overflow and reran with 128 bit arithmetic.
*Input taken from file mit.ine
mit.ine
*mulint : max(a,b) > 2147483647
*redund2 found  restarting
*redund:lrslib v.7.1 2020.5.23(128bit,lrslong.h,overflow checking)
*Input taken from file mit.ine
mit.ine
*row 75 was redundant and removed
*row 77 was redundant and removed
*row 89 was redundant and removed

*row 709 was redundant and removed
Hrepresentation
begin
708 9 rational
36 0 0 2 2 1 0 0 0

0 0 0 0 0 0 0 0 1
end
*Input had 729 rows and 9 columns: 21 row(s) redundant
*Overflow checking on lrslong arithmetic
*redund:lrslib v.7.1 2020.5.23(128bit,lrslong.h)
linearity k i_{1 }i_{2
}i ... i_{k}
The input file contains k linearities. If the input is a Hrepresentation, the rows i_{1 } i_{2 }i ... i_{k }of the input file are equations. For a Vrepresentation, the rows with these indices should begin with zero in column one, and will be interpreted as lines rather than rays. Linearities defined on the input vertices of a Vrepresentation are not defined, but the program will accept them and produce some output. Each of the indice i_{k} must be a distinct number between 1 and m. With an Hrepresentation, linearities are useful for enumeration of vertices on a facet or lower dimensional subspace. For example the file:cube_ridge
*cube of side 2 centred at the origin
Hrepresentation
linearity 2 1 5
begin
6 4 rational
1 1 0 0
1 0 1 0
1 0 0 1
1 1 0 0
1 0 1 0
1 0 0 1
endcauses vertices to be enumerated on the ridge which is the intersection of the two facets
x_{1} = 1 and x_{2} = 1
so the output is the pair of vertices
cube_ridge
*Input linearity in row(s) 1 5
Vrepresentation
begin
2 4 rational
1 1 1 1
1 1 1 1
endSpecifying linearities in this way will often produce redundancy , especially if the dimension of the problem is reduced considerably. As a preprocessing step, it is useful to apply to remove any redundancy by redund. In the case of the above problem the output produced by redund is:
cube
*Input linearity in row(s) 1 5
*row 2 was redundant and removed
*row 4 was redundant and removed
Hrepresentation
linearity 2 1 2
begin
4 4 rational
1 1 0 0
1 0 1 0
1 0 0 1
1 0 0 1and two redundant halfspaces were removed.
Redundant columns are closely related to linearities. If we examine the Vrepresentation of cube_ridge above we can see that it is just a line segment in 3 dimensional space. Further, columns 2 and 3 are multiples of column 1. If lrs is applied to this file, the column redundancies give rise to two linearities, so the output will appear as the Hrepresentation given above: geometrically the intersection of two planes (the linearities) with two halfplanes (defining the endpoints of the line segment).
In general, the representation of the linearity space is not unique, however the one produced by lrs should be the same as that produced by cdd.
....
1 24 48 0 0 0 0 64 0
1 24 48 0 0 0 0 72 0
lrs_lib: checkpointing:
lrs_lib: State #0: (LRS globals)
restart 33 0 12542 8 634 640 641 678 704 725 726 729
integervertices 14
lrs_lib: checkpoint finished
4.476u 0.000s 0:04.49 99.5% 0+0k 0+0io 5657pf+0w
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
end
restart 33 0 12542 8 634 640 641 678 704 725 726 729
integervertices 14
*lrs:lrslib v.7.0 2018.6.14(64bit,lrslong.h,hybrid arithmetic)will complete the full run.
*Input taken from mit.ine
mit.ine
*restart V#33 R#0 B#12542 h=8 facets 634 640 641 678 704 725 726 729
*lrs:overflow possible: restarting with 128 bit arithmetic
1 16 16 8 2 1 4 32 8
1 16 80/3 16/3 0 0 0 64/3 0
1 21 18 9/2 3/2 0 0 24 6
....
The following error messages are produced by lrs . They are arranged in alphabetic order.
Cannot find linearity in the basis
The linearity option was specified but a basis cannot be created. Check the linearity indices are all less than n1 and are disitinct.
Data type must be integer of rational
Usually means that end of file was reached before enough input data was read.
Even with redundant input removed a polyhedron may be highly
degenerate. In distribution directory ine/metric there are many
highly degenerate combinatorial polytopes. These are difficult
problems for all vertex enumeration/convex hull programs that
use pivoting, such as lrs. For example, the file cp6.ine
is a polytope with 368 facets in 16 dimensions. It has 32
vertices, but computing these required the evaluation of
4,844,923,002 bases!(see AvisJordan, 2017)
For degenerate inputs, pivot based methods for vertex/ray enumeration such as lrs may generate the same output ray many times. An output is only printed when it occurs with a lexicographically minimum basis. This removes all duplicate vertices, but rays may still be output more than once. This is due to the fact that duplicate geometric rays cannot always be detected without storing the output. Since Vrepresentations are automatically lifted to a higher dimension, this will not happen for facet enumeration. Unless the allbases option is specified, lrs makes checks in order to remove duplicates. A warning message is produced when duplicates may occur in the output. They can be removed using the program buffer.c. Two important types of input never produce duplicate output: polytopes (i.e. bounded polyhedra) and cones (i.e. polyhedra where the origin is the only vertex).
D. Avis, lrs: A Revised Implementation of the Reverse Search
Vertex Enumeration Algorithm,
http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps
In: Polytopes  Combinatorics and Computation, Ed.
G. Kalai and G. Ziegler, BirkhauserVerlag (2000) 177198.
D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration Algorithm," Optimization Methods and Software, (1998 (to appear)). http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98b.ps
D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory and Applications, Vol 7,pp.265301(1997). http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps
D. Avis and L. Devroye, "Estimating the Number of Vertices of a
Polyhedron," pp. 179190 in Snapshots of Computational and
Discrete Geometry, ed. D. Avis and P. Bose, School of Computer
Science, McGill University (1994).
http://cgm.cs.mcgill.ca/~avis/doc/avis/AD94a.ps
In: Information Processing Letters, (2000) V. 73, pp.
137143.
D. Avis and K. Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra," Discrete and Computational Geometry, Vol. 8, pp. 295313 (1992). http://cgm.cs.mcgill.ca/~avis/doc/avis/AF92b.ps
D. Avis, K. Fukuda and S. Picozzi, "On Canonical Representations of Convex Polyhedra", Mathematical Software, ICMS 2002, Ed. A. Cohen, XS Gao, N. Takayama, World Scientific, pp.350360 (2002) http://cgm.cs.mcgill.ca/~avis/doc/avis/AFP02a.psD. Avis, G. Rosenberg, R. Savani, B. von Stengel, "Enumeration of Nash Equilibria for TwoPlayer Games", Economic Theory 42(2009) 937 pdf
D. Bremner, K. Fukuda and A. Marzetta, PrimalDual Methods for Vertex and Facet Enumeration, 13th ACM Symposium on Computational Geometry SCG 1997, 4956. http://www.cs.unb.ca/profs/bremner/pd/