- Symmetry Points of Convex Set: Basic Properties and Computational Complexity Alexandre Belloni (bellonimit.edu) Robert M. Freund (rfreundmit.edu) Abstract: 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. Keywords: convex geometry, symmetry, polytope, computational complexity Category 1: Convex and Nonsmooth Optimization Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: MIT Operations Research Center Working Paper OR-369-04 Download: [PDF]Entry Submitted: 07/23/2004Entry Accepted: 07/23/2004Entry Last Modified: 07/23/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.