# Computational Convexity

Vorlesung

# Content (from the module handbook)

- Computational Convexity is a special branch of algorithmic geometry with a focus on convex problems in arbitrary dimension (part of the input) and (if helpful) general normed spaces. Many ideas and techniques arise directly from Convex Analysis and Linear Programming.

- In Optimal Containment one wants to find an optimal cover of a given (finite) set by an optimal convex set (a container) chosen from a family of such sets, often generated by certain allowed transformations (like dilatation, translation, rotation, or affinities) of a representative (e.g. a unit ball of a normed space). Also coverings with several containers will be touched.

# News

- 31st of jan: There are several nice video on youtube about bodies of constant width: see for example Bodies of constant width
^{} - 31st of jan: Look here for a detailed description how to get a 3D-model of a Meißner body: Constructing the Meißner bodies
^{} - 16th of jan: Please make an appointment for your oral exam!
- 25th of oct: If "P=NP ?" belongs to the Millenium Prize Problems
^{}. - 17th of oct: There is a nice tool for creating 3D zonotopes yourself: Zonotopebuilder
^{} - 9th of aug: Welcome on the course webpage, more infos are following soon.

# Dates of lectures/exercise classes and office hours

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

Lecture | Thursay | 10.15 - 11.45 | 03.06.011 | Oct, 18th | Feb, 7th | Brandenberg |

Lecture | Friday | 10.15 - 11.45 | 03.06.011 | Oct, 19th | Feb, 8th | Brandenberg |

Exercise Class | Friday | 8.30 - 10.00 | 03.06.011 | Oct, 26th | Feb, 8th | Brandenberg |

# Lecture Notes

- Lecture Notes of the present course will always be uploaded shortly after the according lectures will have been held.
- Since the lecture on Convex Optimization is a prerequisite for this course here are some lecture notes:

- Lecture 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lecture 11
- Lecture 12
- Lecture 13
- Lecture 14
- Lecture 15
- Lecture 16
- Lecture 17
- Lecture 18
- Lecture 19
- Lecture 20
- Lecture 21
- Lecture 22
- Lecture 23
- Lecture 24
- Lecture 25
- Lecture 26
- Lecture 27
- Lecture 28

- Below: complete chapters of the lecture-notes and the full file:

- Chapter 1 - Basics from Convex Analysis
- Chapter 2 - Complexity Theory - A short introduction
- Chapter 3 - Some basic problems in Computational Convexity and Optimal Containment, and Norm Maximization
- Chapter 4 - Containment under homothety
- Chapter 5 - k-Containment
- Chapter 6 - Diameter and width
- Chapter 7 - Containment under linearity and affinity

# Excercises

Problem Sheet | Excercise Class | Solution Outlines |
---|---|---|

Sheet 1 | 2018-10-26 | Sheet 1 |

Sheet 2 | 2018-11-02 | Sheet 2 |

Sheet 3 | 2018-11-09 | Sheet 3 |

Sheet 4 | 2018-11-16 | Sheet 4 |

Sheet 5 | 2018-11-23 | Sheet 5 |

Sheet 6 | 2018-11-30 | Sheet 6 |

Sheet 7 | 2018-12-07 | Sheet 7 |

Sheet 8 | 2018-12-14 | Sheet 8 |

Sheet 9 | 2018-12-21 | Sheet 9 |

Sheet 10 | 2018-12-21 | Sheet 10 |

Sheet 11 | 2019-01-18 | Sheet 11 |

Sheet 12 | 2019-01-25 | Sheet 12 |

Sheet 13 | 2019-02-01 | Sheet 13 |

Sheet 14 | 2019-02-08 | Sheet 14 |

# Oral exams

Please make an appointment as soon as possible!# Literature

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

- Gritzmann. Grundlagen der mathematischen Optimierung (in german)

## On Convex Analysis and Convex Geometry

- Boltyanski, Martini, Soltan. Excursions into Combinatorial Geometry. Springer Universitext, 1997.
- 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

- [Bri02] Brieden. Geometric optimization problems likely not contained in APX. Discrete Comput. Geom., 28:201-209, 2002.
- [BGK+01] Brieden, Gritzmann, Kannan, Klee, Lovasz, Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48:63-105, 2001.
- [BGK00] 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, Gonzalez Merino - The asymmetry of complete and constant width bodies in general normed spaces and the Jung constant , Israel J. Math. 218, No. 1, 489-510 (2017).
- Brandenberg, König. No Dimension Independent Core-Sets for Containment under Homothetics. Discrete Comput. Geom. 49, No. 1, 3-21 (2013).
- Brandenberg, König. Sharpening Geometric Inequalities using Computable Symmetry Measures. Mathematika 61, 559-580 (2015).
- Brandenberg, Roth - New algorithms for k-center and extensions , J. Comb. Optim. 18, 376-392 (2009)
- 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.
- Klee. The critical set of a convex body. Amer. J. Pure Math., 75, 178-188, 1953.
- 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.