next up previous contents
Next: About this document ... Up: Frequently Asked Questions in Previous: Acknowledgements   Contents

Bibliography

ABS97
D. Avis, D. Bremner, and R. Seidel.
How good are convex hull algorithms.
Computational Geometry: Theory and Applications, 7:265-302, 1997.

AF92
D. Avis and K. Fukuda.
A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra.
Discrete Comput. Geom., 8:295-313, 1992.

AF96
D. Avis and K. Fukuda.
Reverse search for enumeration.
Discrete Applied Mathematics, 65:21-46, 1996.

Ame
N. Amenta.
Directory of computational geometry.
http://www.geom.uiuc.edu/software/cglist/.

Avi
D. Avis.
lrs Homepage.
http://cgm.cs.mcgill.ca/~avis/C/lrs.html.

BDH96
C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.
The quickhull algorithm for convex hulls.
ACM Trans. Math. Softw., 22(4):469-483, December 1996.

BDH03
C.B. Barber, D.P. Dobkin, and H. Huhdanpaa.
qhull, Version 2003.1, 2003.
program and report available from http://www.qhull.org/.

BEF00
B. Büeler, A. Enge, and K. Fukuda.
Exact volume computation for convex polytopes: A practical study.
In G. Kalai and G. M. Ziegler, editors, Polytopes - Combinatorics and Computation, DMV-Seminar 29, pages 131-154. Birkhäuser, 2000.

BFM97
D. Bremner, K. Fukuda, and A. Marzetta.
Primal-dual methods for vertex and facet enumeration.
In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 49-56, 1997.

BL98
M.R. Bussieck and M.E. Lübbecke.
The vertex set of a $ 0/1$-polytope is strongly p-enumerable.
Computational Geometry, 11:103-109, 1998.

BMFN96
A. Brüngger, A. Marzetta, K. Fukuda, and J. Nievergelt.
The parallel search bench zram and its applications.
Technical report, ETH Zurich, May 1996.

BMT85
C. Buchta, J. Müller, and R. F. Tichy.
Stochastical approximation of convex bodies.
Math. Ann., 271(2):225-235, 1985.

BP00
I. Bárány and A. Pór.
0-1 polytopes with many facets.
Manuscript, Rényi Institute of Mathematics, Hungarian Academy of Sciences, 2000.
http://www.renyi.hu/~barany/.

CCH53
A. Charnes, W.W. Cooper, and A. Henderson.
An introduction to linear programming.
John Wiley & Sons, Inc., 1953.

Cha93
B. Chazelle.
An optimal convex hull algorithm in any fixed dimension.
Discrete Comput. Geom., 10:377-409, 1993.

Chv83
V. Chvatal.
Linear Programming.
W.H.Freeman and Company, 1983.

CK70
D.R. Chand and S.S. Kapur.
An algorithms for convex polytopes.
J. Assoc. Comput. Mach., 17:78-86, 1970.

CL97
T. Christof and A. Löbel.
PORTA: Polyhedron representation transformation algorithm (ver. 1.3.1), 1997.
http://www.zib.de/Optimization/Software/Porta/.

Cla94
K. L. Clarkson.
More output-sensitive geometric algorithms.
In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., pages 695-702, 1994.
http://cm.bell-labs.com/who/clarkson/pubs.html.

Dan63
G.B. Dantzig.
Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

DF88
M.E. Dyer and A.M. Frieze.
The complexity of computing the volume of a polyhedron.
SIAM J. Comput., 17:967-974, 1988.

Dye83
M.E. Dyer.
The complexity of vertex enumeration methods.
Math. Oper. Res., 8:381-402, 1983.

Ede87
H. Edelsbrunner.
Algorithms in Combinatorial Geometry.
Springer-Verlag, 1987.

Eri
J. Erickson.
Computational geometry pages, list of software libraries and codes.
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/.

FG
R. Fourer and J.W. Gregory.
Linear programming frequently asked questions (LP-FAQ).
http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html.

FLL00
K. Fukuda, Th. M. Liebling, and C. Lütolf.
Extended convex hull.
In D. Bremner, editor, Proceedings of the 12th Canadian Conference on Computational Geometry, pages 57-63, 2000.

FLM97
K. Fukuda, Th. M. Liebling, and F. Margot.
Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
Computational Geometry, 8:1-12, 1997.
ps file available from ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/optvert9610.ps.gz.

FO85
R. Freund and J. Orlin.
On the complexity of four polyhedral set containment problems.
Math. Programming, 33:133-145, 1985.

FR94
K. Fukuda and V. Rosta.
Combinatorial face enumeration in convex polytopes.
Computational Geometry, 4:191-198, 1994.

Fuk
K. Fukuda.
Komei Fukuda's Homepage, McGill University, Montreal, Canada.
http://www.cs.mcgill.ca/~fukuda/.

Fuk02
K. Fukuda.
cdd, cddplus and cddlib homepage.
McGill University, Montreal, Canada, 2002.
http://www.cs.mcgill.ca/~fukuda/software/cdd_home/cdd.html.

Ge97
J.E. Goodman and J. O'Rourke (eds.).
Handbook of Discrete and Computational Geometry.
CRC Press, 1997.

GJ99
E. Gawrilow and M. Joswig.
Polymake, version 1.3, 1999.
http://www.math.tu-berlin.de/diskregeom/http://www.math.tu-berlin.de/diskregeom/.

Kal97
G. Kalai.
Linear programming, the simplex algorithm and simple polytopes.
Math. Programming, 79(1-3, Ser. B):217-233, 1997.
Lectures on mathematical programming (ismp97) (Lausanne, 1997), ps file available from http://www.ma.huji.ac.il/~kalai/papers.html.

Kar84
N. Karmarkar.
A new polynomial-time algorithm for linear programming.
Combinatorica, 4:373-395, 1984.

Kha79
L.G. Khachiyan.
A polynomial algorithm in linear programming.
Dokklady Akademiia Nauk SSSR, 244:1093-1096, 1979.

Kha93
L.G. Khachiyan.
Complexity of polytope volume computation.
In J. Pach, editor, New Trends in Discrete and Computational Geometry, pages 91-101. Springer Verlag, Berlin, 1993.

LS93
L. Lovasz and M. Simonovits.
Random walks in a convex body and an improved volume algorithm.
Random structures & algorithms, 4:359-412, 1993.

Lüb99
M.E. Lübbecke.
zeRone: Vertex enumeration for $ 0-1$ polytopes (ver. 1.8.1), 1999.
http://www.math.tu-bs.de/mo/research/zerone.html.

Mar97
A. Marzetta.
pd - C-implementation of the primal-dual algoirithm, 1997.
code available from http://www.cs.unb.ca/profs/bremner/pd/.

McM70
P. McMullen.
The maximum number of faces of a convex polytope.
Mathematika, XVII:179-184, 1970.

MRTT53
T.S. Motzkin, H. Raiffa, GL. Thompson, and R.M. Thrall.
The double description method.
In H.W. Kuhn and A.W.Tucker, editors, Contributions to theory of games, Vol. 2. Princeton University Press, Princeton, RI, 1953.

MS71
P. McMullen and G.C. Shephard.
Convex polytopes and the upper bound conjecture.
Cambridge University Press, 1971.

Mul94
K. Mulmuley.
Computational Geometry, An Introduction Through Randamized Algorithms.
Prentice-Hall, 1994.

O'R
J. O'Rourke.
comp.graphics.algorithms FAQ.
http://www.faqs.org/.

OSS95
Th. Ottmann, S. Schuierer, and S. Soundaralakshmi.
Enumerating extreme points in higher dimensions.
In E.W. Mayer and C. Puech, editors, STACS 95: 12th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 900, pages 562-570. Springer-Verlag, 1995.

Rot92
G. Rote.
Degenerate convex hulls in high dimensions without extra storage.
In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 26-32, 1992.

RTV97
C. Roos, T. Terlaky, and J.-Ph. Vial.
Theory and Algorithms for Linear Optimization: An Interior Point Approach.
John Wiley and Sons, 1997.

Sch86
A. Schrijver.
Theory of Linear and Integer Programming.
John Wiley & Sons, New York, 1986.

Sei86
R. Seidel.
Constructing higher-dimensional convex hulls at logarithmic cost per face.
In 18th STOC, pages 404-413, 1986.

Sei91
R. Seidel.
Exact upper bounds for the number of faces in $ d$-dimensional Voronoi diagram.
In P. Gritzmann and B. Sturmfels, editors, Applied Geometry and Discrete Mathematics - The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 517-529. Amer. Math. Soc., Providence, RI, 1991.

Sey94
P.D. Seymour.
A note on hyperplane generation.
J. Combin. Theory, Series B, 61:88-91, 1994.

Yap00
C.K. Yap.
Fundamental problems in algorithmic algebra.
Oxford University Press, New York, 2000.

Zie94
G.M. Ziegler.
Lectures on polytopes.
Graduate Texts in Mathematics 152. Springer-Verlag, 1994.



Komei Fukuda 2004-08-26