Finishing Guler, Chapter 3 and starting Chapter 4.

Class notes (pretty incomplete, to be used just as a study guide), here and here.

Using linear constraints compatibility in packing problems, see e.g. here.

**Exercises**:

- Can a triangle on plane be a linear image of a cube (in a high-dimensional space)?
- Is the set of positive polynomials (i.e. such that \(p(x)>0\) for any \(x\)) convex?
- Represent \(n\times n\) matrix with all coefficient \(1/n\) as a convex combination of permutation matrices.
- Find the Minkowski sum of three segments, \([(0,0),(0,1)], [(0,0),(1,0)],[(0,0),(-1,1)]\).

**Homework** (due by midnight of Tuesday, Feb. 19).

- Consider the function

\[

f(x,y)=(y^4+2y^2+2)x^2-2(y^2+1)x+1.

\]

Find \(\inf_{x,y}f(x,y)=:c\). Find a sequence of points \(p_n=(x_n,y_n)\) such that the function converges to its \(\inf\) and its gradient converges to zero: \(f(p_n)\to c; \nabla f(p_n)\to 0\). - Describe Minkowski sum of the unit circle and positive orthant \(\{(x\geq 0, y\geq 0\}\).
- Consider the function

\[

g(x,y)=\ln(e^x+e^y+e^{-x-y}).

\]

Find the range of the gradient of \(g\), that is all the vectors

\[

(p,q)=\left(\frac{\partial g}{\partial x},\frac{\partial g}{\partial y}\right).

\] - On the plane, a collection of vertical intervals \(I_k:=[(x_k,y_k^-),(x_k,y_k^+)], k=1,\ldots, K\) has the property that for any three of these intervals, there exists a straight line intersecting all three of them. Is it true that there is a straight line intersecting all \(K\) intervals?
- Find the largest radius \(r\) such that three non-overlapping open disks of radius \(r\) can fit into the unit square.

What particular results or theorem are we expected to use regarding problem 3?

You can use basic definitions

What does it mean by “describe the Minkowski sum … “? Do we describe the region by words or draw a picture?

Picture or formula (with explanation how you arrive at it), – either will do.

What is the exact deadline for this assignment? The gradescope indicates that the midnight of Monday, Feb.18 is the deadline, but according to this page, the midnight of Feb.19 is the deadline.

Midnight of Tuesday, Feb 19. Sorry about the confusion.

Can we get some hint or an example of vertical interval for problem 4? I am not sure where to start. Thanks!

What is a straight line on the plane? Unless it is vertical (rarely answers the question!), it is given by \(\{y=ax+b\}\). What are the conditions on \(a,b\) to intersect a segment?

Can we get some hint for Problem 5? Plus, can we give an approximate solution for this problem?

Use necessary conditions outlined int he lecture to enumerate possible optimal configurations of the disks.

Approximate to 15 digits or an exact formula is fine.

In this image (https://imgur.com/lljoHQ4), there doesn’t appear to be any way for the right-most interval to be intersected while the other intervals are also intersected. In order for the right-most interval to be intersected, it would have to be moved up so that it lies in the shaded region.

How can three arbitrary vertical line segments in R^2 be intersected with a straight line? It seems like there must be some strict conditions on the vertical intervals for this to be true.

This picture is a nice illustration of a collection of segments which

does nothave the property stipulated in the problem, “that for any three of these intervals, there exists a straight line intersecting all three of them.”I thought that the definition of vertical intervals, Ik:=[(xk,y−k),(xk,y+k)], indicate that we can have intervals such as (1,1),(1,-1) or (-3,5), (-3,-5) such that the y-coordinate has a change of sign. Isn’t this true?

For problem 4 is it sufficient to show that the set of lines that cross a certain interval is convex then apply helly’s theorem?

Perhaps.

I’m still struggling with Problem 5. Can we have a bit more hints, maybe some reference of book chapters or web links? I’m still confused about what is the function that we should optimize.

Leture notes talk about packing disks. Also there is a link on this very page to relevant paper.