Takeshi Tokuyama
Tohoku University, Japan
Abstract: Computational geometry is a field in theoretical computer science to handle geometric data processing. It is widely applied in engineering and science, while the long history of mathematics supports its development.
Among many topics in computational geometry, convex hull computation is a popular and fundamental problem. The speaker will introduce his recent lucky encounter with classical mathematics to study variants of convex hull problems. The first one is the area-minimization of planar convex hull of movable objects (in particular a set of n segments under translation). We can compute this variant in O(n log n) time by using long history on Kakeya's problem (proposed in 1917 by a Japanese mathematician Soichi Kakeya). The second one is the concept of consistent digital lines that is required to define convex hull in grid geometry. Here, we encounter classical discrepancy theory to deal with a key problem (indeed, it was re-discovery of a report by Ruby in 80th ), and it was successfully generalized to a construction of consistent digital lines by Christ et.al.
References:
1. Hee-Kap Ahn, Samg Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama and Antoine Vigneron: A Generalization of the Convex Kakeya Problem, to appear in LATIN 2012.
2. Jinhee Chun, Matias Korman, Martin Nöllenburg, Takeshi Tokuyama: Consistent Digital Rays. Discrete & Computational Geometry 42(3): 359-378 (2009)
3. Tobias Christ, Dömötör Pálvölgyi, Milos Stojakovic: Consistent digital line segments. Symposium on Computational Geometry 2010: 11-18