NoDI seminar

Connectivity in Semialgebraic Sets

Hoon Hong 15:00, June 4, 2014 G-610 New Main Building, Beihang University

Abstract: A semialgebraic set is a subset of real space defined by polynomial equations and inequalities. A semialgebraic set is a union of finitely many maximally connected components. In this talk, we consider the problem of deciding whether two given points in a semialgebraic set are connected, that is, whether the two points lie in a same connected component. In particular, we consider the semialgebraic set defined by f not equal 0 where f is a given bivariate polynomial. The motivation comes from the observation that many important/non-trivial problems in science and engineering can be often reduced to that of connectivity. Due to its importance, there has been intense research effort on the problem. We will describe a method based on gradient fields and provide a sketch of the proof of correctness based Morse complex. The method seems to be more efficient than the previous methods in practice. This is a joint work with James Rohal, Mohab Safey El Din, and Erich Schost.

Poster Slides Photos

Past talks