North Carolina State University
Connectivity in Semialgebraic Sets
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 thant the previous methods in practice. We will also provide a bound on the length of the curves connecting the points.
This is a joint work with James Rohal, Mohab Safey Eldin, and Erich Schost.