Symmetry Points of Convex Set: Basic Properties and Computational Complexity

Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x - y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. We call x^* a symmetry point of S if x^* achieves the above supremum. These symmetry measures are all invariant under invertible affine transformation and/or change in norm, and so are of interest in the study of the geometry of convex sets. In this study we demonstrate various properties of sym(x,S), including relations with convex geometry quantities like volume, distance and diameter, and cross-ratio distance. When S is polyhedral of the form {x : Ax \le b}, there is an interior-point algorithm that will compute an approximation of sym(S) in O(m^1.5 ln(m / \epsilon)) iterations of Newton's method.

Citation

MIT Operations Research Center Working Paper OR-369-04