Separation of convex polyhedral sets with uncertain data

Abstract

We study separation of convex polyhedra (described by systems of linear inequalities or by their lists of verices) under uncertainty, which is treated by interval analysis. We propose a way how to check whether given convex polyhedra are separable for some or for all realizations of the interval data.

Some of the proposed problems can be checked efficiently, while the others are NP-hard.

Keywords

• Separation
• convex
• polyhedral
• uncertain
• data