Computational Convexity - Optimal Containment (MA5206)
## lecture |

lecturer: | Rene Brandenberg %SBBANNER% |
---|---|

learning assistant and organization: | Rene Brandenberg %SBBANNER% |

News | Dates of lectures/exercise classes and office hours | Lecture notes | Tutorials | Exercise sheets | Literature | FAQ |

## News

- (2012-07-08) Problem sheet 10 updated (correction of the definition of inner radii)
- (2012-06-30) Please contact me soon, if you want to fix a date for the oral exam.
- (2012-06-18) Problem sheet 7 updated (correction of relevant typing errors in 7.1 and 7.4)
- (2012-05-24) Problem sheet 5 updated (5.1 (c) added)
- (2012-05-19) Next week there will be an exercise class on tuesday (May, 22nd) and a normal lecture on thursday (May, 24th)
- (2012-05-10) Problem sheet 3 corrected!
- (2012-05-07) Please notice that we have changed the starting times of the lectures again.
- (2012-05-03) Next thursday, 10th of may is again a normal lecture. The excercise class will take place at monday, 14th.
- (2012-04-18) This week there will be a normal lecture instead of an exercise class at thursday 8.30. In the two weeks after pentecost I'm not at TU, so that I would miss an excercise class and two lectures. One of the lectures is replaced by the lecture this thursday. The others (exercise and lecture) will most probably be taught by Stefan König. Details will be given later (here and within the lectures)

## Dates of lectures/exercise classes and office hours

type | day | time | room | starting date | closing date | teacher |
---|---|---|---|---|---|---|

lecture | monday | 12:30 a.m. to 2:00 p.m. | 02.08.011 | april 16th | july 16th | René Brandenberg |

lecture | tuesday | 12:15 a.m. to 1:45 p.m. | 02.08.011 | april 17th | july 17th | René Brandenberg |

excercise | thursday | 8:30 a.m. to 10:00 a.m. | 02.08.011 | april 19th | july 19th | René Brandenberg |

## Lecture Notes

Datum | Datei | Themen |
---|---|---|

2012-04-16 | slides of the introductory talk | |

2012-04-17 | lecture1: basics from convex analysis/geometry, part 1 | |

2012-04-17 | lecture2: basics from convex analysis/geometry, part 2 | |

2012-04-23 | lecture3: complexity theory: basics | |

2012-04-24 | lecture4: complexity theory: NP-hardness | |

2012-04-30 | lecture5: complexity theory: some reductions | |

2012-05-07 | lecture6: complexity theory: optimization problems | |

2012-05-08 | lecture7: norm maximization | |

2012-05-10 | lecture8: mcp-hom, foundations, part 1 | |

2012-05-15 | lecture9: mcp-hom, foundations, part 2 | |

2012-05-21 | lecture10: mcp-hom, exact algorithms | |

2012-05-24 | lecture11: mcp-hom, euclidean algorithms | |

2012-05-28 | lecture12: core sets for euclidean containers | |

2012-06-11 | lecture13: core set bounds for general (symmetrric) containers | |

2012-06-12 | lecture14: helly dimension and a cutting plane approach | |

2012-06-18 | lecture15: k-containment, definitions and hardness results | |

2012-06-19 | lecture16: k-containment, diameter partitioning | |

2012-06-25 | lecture17: k-containment, branch-and-bound algorithm | |

2012-06-26 | lecture18: diameter+width, definitions and lemmas | |

2012-07-02 | lecture19: diameter+width, more lemmas | |

2012-07-03 | lecture20: diameter+width, algorithms | |

2012-07-09 | lecture21: diameter+width, complexity | |

2012-07-10 | lecture22: successive radii, definitions | |

2012-07-16 | lecture23: successive radii, complexity and approximation | |

2012-07-17 | lecture24: mcp-lin and mcp-aff |

## Exercises

Problem Sheet | Exercise Class | Solutions |
---|---|---|

Sheet 1 | 2012-04-26 | Sheet 1 |

Sheet 2 | 2012-05-03 | Sheet 2 |

Sheet 3 | 2012-05-14 | Sheet 3 |

Sheet 4 | 2012-05-22 | Sheet 4 |

Sheet 5 | 2012-06-04 | Sheet 5 |

Sheet 6 | 2012-06-14 | Sheet 6 |

Sheet 7 | 2012-06-21 | Sheet 7 |

Sheet 8 | 2012-06-28 | Sheet 8 |

Sheet 9 | 2012-07-05 | Sheet 9 |

Sheet 10 | 2012-07-12 | Sheet 10 |

## Literature

### In General (Convex Analysis, Optimization, and Complexity Theory)

- Gritzmann. Vieweg Studium, Nr.90, Optimierung (german, not yet available)

### On Convex Analysis and Convex Geometry

- Rockafellar. Convex Analysis. Princeton University Press, 1996.
- Schneider. Convex Bodies: The Brunn-Minkowski Theory, 2008.
- Ziegler. Lectures on Polytopes, 2008.

### On Complexity Theory

- Garey, Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness,1979.
- Papadimitriou. Computational Complexity, 1994.
- Wegner. Complexity Theory: Exploring the Limits of Efficient Algorithms, 2005.

### Special Papers On Norm Maximization

- Brieden. Geometric optimization problems likely not contained in APX. Discrete Comput. Geom., 28:201-209, 2002.
- Brieden, Gritzmann, Kannan, Klee, Lovasz, Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48:63-105, 2001.
- Brieden, Gritzmann, Klee. Inapproximability of some geometric and quadratic optimization problems. In P.M. Pardalos, editor, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, p. 96-115. Kluwer, 2000.

### Special Papers On Radii And Containment

- Brandenberg, König. No Dimension Independent Core-Sets for Containment under Homothetics. arXiv:1010.4229v1.
- Gärtner. Fast and robust smallest enclosing balls. In Proc. 7th Annu. European Sympos. Algorithms, volume 1643 of Lecture Notes in Comput. Sci., p. 325-338. Springer-Verlag, 1999.
- Gritzmann, Habsieger, Klee. Good and bad radii of convex polygons. SIAM J.Comput., 20(2):395-403, 1991.
- Gritzmann, Klee. Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280, 1992.
- Gritzmann, Klee. Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program., 59:163-213, 1993.
- Grünbaum. Measures of symmetry for convex sets. Proc. Symp. Pure Math., 1 (Convexity), p. 271-284, 1963.
- Sharir, Welzl. A combinatorial bound for linear programming and related problems. In A. Finkel and M. Jantzen, editors, STACS 92, volume 577 of Lecture Notes in Comput. Sci., p. 567-579. Springer Berlin / Heidelberg, 1992.

## What is Computational Convexity?

Also sometimes seen as some part of Computational Geometry, the main ideas and techniques of Computational Convexity have their origin in fields like Linear Programming, Polyhedral Combinatorics, and Algorithmic Theory of Convex Bodies, all subsummable backwardly under the notion of Computational Convexity. Two focuses describe the main difference betweeen Computational Convexity and typical Computational Geometry: First, instead of the typical euclidean geometry often general normed spaces are considered, and secondly, the dimension is part of the algorithmic input, as, e.g., typical in Linear Programming.## What is Optimal Containment?

In a basic Optimal Containment problem we want to compute (or approximate) extremal representatives within a given family of convex bodies , contained in or containing a fixed set. For example, given a set of points one wants to find the smallest %$n$%-dimensional cube containing it, where smallest means the scaling factor (the dilatation) and the considered family is the orbit of the standard unit cube under homothetics (dilatation and translation) or similarities (allowing also rotations). A special case of Optimal Containment are radii of convex sets. The computation of the four basic radii (inner- and outer radius, width and diameter) is a classical problem in convex geometry. Generalizing and unifying these, several series of succesive inner and outer radii of convex bodies maybe considered. E.g. the radius of a largest %$j$%-dimensional ball contained in a given set connects diameter (1-dimensional ball) and inradius (d-dimensional) ball.An optimal embedding for maximizing the radius of a disc (a 2-dimensional ball) in a 3-dimensional cube, an inner 2-radius of that cube.