School of Computing, KAIST

^{2}) 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.

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

The reverse Kakeya problem

Otfried Cheong

School of Computing, KAIST

School of Computing, KAIST

2017/3/20 Tue 5PM

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^{2}) 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.

Putting your coin collection on a shelf

Otfried Cheong

School of Computing, KAIST

School of Computing, KAIST

2017/04/03 Monday 4PM-5PM

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.

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.

A generalization of Kakeya’s problem

Otfried Cheong

Department of Computer Science, KAIST

Department of Computer Science, KAIST

2011/4/14 Thu 4:30PM-5:30PM

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.

Helly-Type Theorems for Line-Transversals to Spheres

Otfried Cheong

Div. of Computer Science, KAIST, Daejeon, Korea.

Div. of Computer Science, KAIST, Daejeon, Korea.

2008/03/06 Thu, 3PM-4PM

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.