Search

Algorithms for the Determination of Convex Hulls resp for the Exploration of all Vertices of a Polyhedron


The aim is to discover and to explore the total structure of the polytope, which has been generated as the convex hull of m given points. A computationally fast method for achieving that goal is of eminent importance, in particular in the control of movements or in optimization problems, which have to be treated online.
For solving that problem we have the choice between several algorithms and algorithmic philosophies. Of special importance are incremental and sequential algorithms. We try to carry out a comparison of the quality of these algorithms. In particular, we are interested in an average case analysis of their behavior and a judgment on that basis.
Part of this project is also multiobjective programming, i. e. the exploration of all points of the polytope or polyhedron, which cannot be replaced by other points that are strictly better in all objectives under consideration.

Scientists