This is an FAQ of geometric computation, focused
on Convex Hull, Vertex Enumeration, Voronoi Diagram, Delaunay Triangulation
computation in general dimensions.
Two versions:
html version
or
pdf file.
I have just updated cdd+ (to ver.076a), see
cdd homepage. A new callable library version of cdd has been
released on March 9, 2001 as cddlib-091d which can be used as a standalone program
and can run in floating point arithmetic with both C double and
in rational arithmetic with GMP rational.
International Congress of Mathematical Software, 2002
A Satellite Conference of ICM 2002, Beijing, August 17-19, 2002.
call for papers.
Older Links
Strange Unfoldings of Convex Polytopes
Some interesting unfoldings against human intuition. Click
here for ingenious examples by M. Namiki, T. Matsui and G. Rote.
Research Activities
Polyhedra Project
This is a joint project with David Avis of McGill University, Canada.
It is to develop efficient algorithms and computer programs to compute
all vertices of a given convex polyhedron P = { x : A x <= b}, for a given
real/rational matrix A and a vector b.
There are two codes available, the reverse search code
lrs by Avis and the double description code cdd by Fukuda,
from the following sites. Note that lrs is efficient for
nondegenerate or slightly degenerate inputs and cdd is efficient for
highly degenerate inputs.
To get Avis' reverse search code in C, click
lrs (the most recent version is 3.*)
To get Fukuda's double description code in C and C++, click
cdd Homapage
The graphics generated by SimplexApp (by G. Studer, G. Fankhauser and B. Mateev)
with cdd.
Click here for its homepage.
The main goal of the project is to combine the most advanced technology
of optimization and geometric computation, and to develop new
state-of-the-art theory, techniques and software. The project
started September 1996 and the research subjects being investigated
include:
An adaptive algorithm for vector partitioning
(with Shmuel Onn and Vera Rosta) (
aavp011105.ps.gz).
Cuts, zonotopes and arrangements
(with Jean-Albert Ferrez and Thomas Liebling)
(
cutzono_art011105.ps.gz), and some instances of the 0-1 quadratic programming
with (
exact solutions ).
Complete combinatorial generation of small point configurations
and hyperplance arrangements, an extended abstract (with Lukas Finschi)
(
genconf010430.ps.gz).
Generation of oriented matroids (with Lukas Finschi)
(
GenOM010511.ps.gz), to appear in Disc. Comp. Geometry.
On the skeleton of the metric polytope (with A. Deza, D. Pasechnik and M. Sato)
(
jcdcg13.ps.gz), to appear in Lecture Notes in Computer Science, Springer.
Extended convex hull (with Christine Luetolf and Thomas H. Liebling)
(
ECH000704.ps.gz), to appear in Computational Geometry.
A polynomial case of unconstrained zero-one quadratic
optimization (with Kim Allemand, Thomas M.Liebling, Erich Steiner)
(
QP01paper2.ps.gz), to appear in Math. Programming.
Convexity recognition of the union of polyhedra (with Alberto Bemporad and Fabio D. Torrisi)
(
polyunion001120.ps.gz), to appear in Computational Geometry.
Cocircuit graphs and efficient orientation reconstruction in oriented matroids (with Eric Babson and Lukas Finschi)
(
cgeor000720.ps.gz), to appear in Europ. J. Combin.
On the existence of a short admissible pivot sequences
for feasibility and linear optimization problems (with T. Terlaky, revised on Feb. 14, 2000)
ps version or
pdf version , appeared in Mathematics of Optimization.
Optimization over k-set polytopes and efficient k-set enumeration (with A. Andrzejak)
extended abstract (
kset990112.ps.gz ).
On the cocircuit-graph of an oriented matroid (with R. Cordovil and A. Guedes de Oliveira)
newly revised paper (
cocirgr990303.ps.gz), appeared in Disc Comp Geom 24:257-265(2000).
Towards a unified framework for randomized pivoting algorithms in linear programming (with L. Finschi and H.-J. Luethi)
(randsimp9810.ps.gz).
