OtfriedCheong

Archive of posts with tag 'OtfriedCheong'

  • Otfried Cheong, Putting your coin collection on a shelf
    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.
    Tags:

  • Otfried Cheong, The reverse Kakeya problem
    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.
    Tags:

  • Otfried Cheong, A Generalization of Kakeya’s Problem
    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.</p>

    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.

    Tags:

  • Otfried Cheong, Helly-Type Theorems for Line-Transversals to Spheres
    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.</div>

    Tags:

Monthly Archives