Activity‎ > ‎

GAIA Lecture Series - Chee K.Yap(Courant Institute, New York University)

posted Jul 22, 2012, 5:43 PM by Jihye Jung   [ updated Jul 22, 2012, 5:48 PM ]
 
 - Speaker : Chee K.Yap(Courant Institute, New York University)
- Lecture 1

✎Title :Towards Exact Numerical Voronoi Diagrams

✎Place : Math Science Building room 208

✎Date & Time : July 6, 2012 & 16:00 - 18:00

✎ Abstract

: Voronoi diagrams are extremely versatile as a data structure in many geometric applications. Computing this diagram ``exactly'' for a polyhedral set in 3-D has been a quest of computational geometers for over two decades; this quest is still unrealized.  We locate the difficulty in this quest, thanks to a recent result of Everett et al (2009). More generally, it points to the need for alternative computational models, and other notions of exactness. We consider an alternative approach based on the well-known Subdivision Paradigm. A brief review of such algorithms for Voronoi diagrams is given. Our unique emphasis is the use of purely numerical primitives. We avoid exact (algebraic) primitives because (1) they are hard to implement correctly, and (2) they fail to take full advantage of subdivision.Our approach is captured by ``soft primitives''
that conservatively converge to the exact ones in the limit. We illustrate our approach by designing the first purely numerical algorithm for the Voronoi complex of a non-degenerate polygonal set. We also feature the critical role "Filters" in such algorithms. We will demo our preliminary implementations. Joint work with Vikram Sharma (IMSc) and Jyh-Ming Lien (GMU)

 

 - Lecture 2

✎Title : Pi = 3.14159... is in Log Space

✎Place : Math Science Building room 404

✎Date & Time : July 13, 2012 & 16:00 - 18:00

✎ Abstract

: A real number is in "Log space" if its $n$-th bit ($n\in\ZZ$) can be computed in logarithmic space (Log).
We show that Pi=3.14159... is in Log.This implies that Pi is in the complexity class SC. The latter result was widely assumed to be true from famous BBP algorithm for Pi by Bailey, Borwein and Plouffe. But Knuth, and independently Lipton, pointed out that it is unclear that the BBP algorithm implies such a result. To resolve this issue, we provide a new algorithm for Pi. Our result extends to other constants such as log 2 or square of Pi that also possess two essential ingredients: they have BBP-like series and have bounded irrationality measures.

 

  - Lecture 3

✎Title :Motion Planning and Theory of Soft Subdivision Search

✎Place : Math Science Building room 404

✎Date & Time : July 20, 2012 & 16:00 - 18:00

✎ Abstract

: We propose to design motion planning algorithms using two ingredients: the subdivision paradigm coupled
with ``soft predicates''.  Such predicates are conservative and convergent relative to traditional exact predicates. This leads to the concept of ``resolution-exact'' algorithms. Resolution-exactness contains inherent indeterminacies and other subtleties. We describe an algorithmic framework called``Soft Subdivision Search'' (SSS) for designing such algorithms. There are many parallels between our framework and the well-known Probabilistic Road Maps (PRM) framework. Both frameworks lead to algorithms that are
highly practical, easy to implement, have adaptive and local complexity. The critical difference is that SSS avoids the Halting Problem of PRM. We demonstrate the ease of designing soft predicates for various motion planning problems. The SSS framework provides a theoretically sound basis for new classes of algorithms in motion planning and beyond. Such algorithms are novel, even in the exact case. Our current implementation shows that such algorithms are not only sound and simple to implement, but also efficient in practice. Joint Work with Yi-Jen Chiang and Cong Wang.

 

                   Correspondence: 안희갑 교수(POSTECH, E-mail: heekap@postech.ac.kr, Tel. 279-2387)

Comments