Posts Tagged ‘OtfriedCheong’

Otfried Cheong, The reverse Kakeya problem

Friday, March 2nd, 2018
The reverse Kakeya problem
Otfried Cheong
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 n2) 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.

Otfried Cheong, Putting your coin collection on a shelf

Saturday, March 18th, 2017
Putting your coin collection on a shelf
Otfried Cheong
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.

Otfried Cheong, A Generalization of Kakeya’s Problem

Monday, March 21st, 2011
A generalization of Kakeya’s problem
Otfried Cheong
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.

Otfried Cheong, Helly-Type Theorems for Line-Transversals to Spheres

Friday, August 22nd, 2008
Helly-Type Theorems for Line-Transversals to Spheres
Otfried Cheong
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 Rd. In particular, we show that a family of n ≥ 2d disjoint unit spheres in Rd 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.