Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Inequations, Polyhedra and polytopes
Posted:
Jul 3, 1996 5:34 PM
|
|
Dear Colleagues,
Earlier (in article 5727), Patricia Mainguet asked about the status
of research in linear semialgebraic sets, i.e., computational convexity.
Jeff Erickson replied soon after (in article 5750) and now I'll add my two
cents worth...
Yes, computational convexity is alive and well and thriving.
For example, you can look at the journal
Discrete and Computational Geometry
and see the wealth of papers on polyhedral algorithms over the (at least)
last decade.
As for references, I can add a few more nice books to Jeff's
recommendations:
For discussions on algorithms for (and the complexity of)
convex hull computation (and finding polyhedral faces), you should
try the following three books:
Computational geometry : an introduction / Franco P. Preparata,
Michael Ian Shamos.
New York : Springer-Verlag, c1985.
Texts and monographs in computer science,
Algorithms in combinatorial geometry / Herbert Edelsbrunner.
Berlin ; New York : Springer-Verlag, c1987.
EATCS monographs on theoretical computer science ; v. 10, and
Computational geometry : an introduction through randomized
algorithms / Ketan Mulmuley.
Englewood Cliffs, N.J. : Prentice-Hall, c1994 [i.e., 1993].
(The first two are very illuminating. I've not had a chance
to look through the third yet, but I've heard it's excellent.)
A book illustrating the depth and scope of convex geometry,
via the works of one of the masters, is:
Applied geometry and discrete mathematics : the Victor Klee
festschrift / Peter Gritzmann, Bernd Sturmfels, editors.
: Association for Computing Machinery, c1991.
Klee, Victor.
DIMACS series in discrete mathematics and theoretical computer
science ; v. 4
A book which gives concrete answers to many of the myriad of
natural combinatorial questions one could ask is:
Computational synthetic geometry / Jurgen Bokowski, Bernd
Sturmfels.
Berlin ; New York : Springer-Verlag, c1989.
Sturmfels, Bernd, 1962
Lecture notes in mathematics (Springer-Verlag) ; 1355.
More recently, convex geometry has been applied in a
big way to many problems involving polynomial systems. An
excellent and timely book is:
Grobner bases and convex polytopes / Bernd Sturmfels.
University lecture series (Providence, R.I.) ; 8.
Delving further into this area, there are actually
a number of polyhedral (and NON Grobner-theoretic) algorithms for finding the
roots of a system of polynomial equations. In fact, one can
also relate the number of solutions to polytope volumes. These
remarkable facts are contained in a number of research papers over
the past two decades, and I can supply a bibliography if anyone is
interested.
Hope this helps.
Convexly Yours,
Maurice
|
|
|
|
