KAIST Discrete Math Seminar

We prove a generalization of Pal’s 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360 degrees inside Q. We also prove a lower bound of Ω(m n²) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.

Imagine you want to present your collection of n coins on a shelf, taking as little space as possible – how should you arrange the coins?
More precisely, we are given n circular disks of different radii, and we want to place them in the plane so that they touch the x-axis from above, such that no two disks overlap. The goal is to minimize the length of the range from the leftmost point on a disk to the rightmost point on a disk.
On this seemingly innocent problem we will meet a wide range of algorithmic concepts: An efficient algorithm for a special case, an NP-hardness proof, an approximation algorithm with a guaranteed approximation factor, APX-hardness, and a quasi-polynomial time approximation scheme.

One version of Kakeya’s problem asks for the smallest convex garden in which a ladder of length one can be rotated fully. The answer to this question was shown to be the equilateral triangle of height one by Pal in 1920.

We consider the following generalization: Given a (not necessarily finite) family F of line segments in the plane, what is the smallest convex figure K such that every segment in F can be translated to lie in K?

We show that as in the classic case, the answer can always be chosen to be a triangle. We also give an O(n log n) time algorithm to compute such an optimal triangle if F consists of n line segments.

Joint work with Sang Won Bae, Hee-Kap Ahn, Joachim Gudmundsson, Takeshi Tokuyama, and Antoine Vigneron.

We prove Helly-type theorems for line transversals to disjoint unit spheres in R^d. In particular, we show that a family of n ≥ 2d disjoint unit spheres in R^d has a line transversal if, for some ordering of the balls, any subfamily of 2d balls admits a line transversal consistent with this ordering. We also discuss generalizations that drop the ordering requirement and to spheres with arbitrary radius.