A semi-algebraic set is a subset of real space defined by polynomial equations and inequalities and is a union of finitely many maximally connected components. In this thesis we consider the problem of deciding whether two given points in a semi-algebraic set are connected; that is, whether the two points lie in the same connected component. In particular, we consider the semi-algebraic set defined by f ≠ 0 where f is a given polynomial. The motivation comes from the observation that many important or 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 symbolic-numeric method for solving this problem based on gradient ascent. In the first part of this thesis we will describe the symbolic part of the method. In a forthcoming second paper, we will describe the numeric part of the method. The second part of this thesis focuses on proving the partial correctness and termination of the symbolic method assuming the correctness of the numeric part. In the third part of the thesis we give an upper bound on the length of a path connecting the two input points if they lie in a same connected component. In the last part of the thesis we give experimental timing results for the symbolic-numeric method.
|School:||North Carolina State University|
|School Location:||United States -- North Carolina|
|Source:||DAI-B 76/05(E), Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Mathematics|
|Keywords:||Connectivity, Morse theory, Motion planning, Semi-algebraic sets|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be