Please use this identifier to cite or link to this item:
Title: Upper and Lower Complexity Bounds for Some Problems in Elementary Geometry
Authors: GRIMSON, Rafael 
Advisors: KUIJPERS, Bart
Heintz, Joos
Issue Date: 2010
Abstract: This thesis is mainly dedicated to the study of upper and lower complexity bounds of some problems in the context of semi-algebraic geometry. We present a brief summary of its contents. In Chapter 1 we analyze the algebraic complexity of the linear programming feasibility problem over the reals and prove non-trivial lower bounds for this problem. The linear programming feasibility problem can be stated as follows: given positive integers m > n, a matrix H ∈ Rm×n and a vector h ∈ Rm decide whether there exists a column vector x ∈ Rn such that H · x ≤ h. For the case of polyhedra defined by 2n halfspaces in Rn , we prove that the set I (2n,n) of parameters describing non-empty polyhedra, has an exponential number of limiting hypersurfaces. From this geometric result we obtain, as a corollary, the existence of a constant c > 1 such that, if dense or sparse representation is used to encode polynomials, the length of any quantifier-free formula expressing the set I (2n,n) is bounded from below by Ω(c n ). Other related complexity results are stated; in particular, a lower bound for algebraic computation trees based on the notion of limiting hypersurface is presented. In Chapter 2, we study the sign condition problem for any given a family of polynomials. Essentially, the problem consists in determining the sign condition satisfied by a fixed family of polynomials at a query point, performing as little arithmetic operations as possible. After defining precisely the sign condition and the point location problems, we introduce a method called the dialytic method to solve the first problem efficiently. This method involves a linearization of the original polynomials and provides the best known algorithm to solve the sign condition problem. Finally, using a technique that resembles that of Chapter 1, we prove a lower bounds showing that the dialytic method is almost optimal. In Chapter 3, we discuss different data structures that can be used to solve the point location problem for a given family of polynomials. This problem asks to determine, not only the sign condition satisfied by a family of polynomials at a query point, but also the connected component of the realization of this sign condition containing the query point. After showing how to adapt the dialytic method to this problem, we introduce, In Section 3.3, a method based on an Adapted Cylindrical Algebraic Decomposition of the space that solves the point location problem for any given family. In Section 3.4, we discuss the case of polynomials with integer coefficients given in dense bit representation introducing a method that, based on diophantine geometry, solves the point location problem for generic families of polynomials. We include a brief discussion of the local ray shooting problem. In Chapter 4, we introduce the notion of intrinsic description of a linearlyconstructible set and study the complexity of quantifier-elimination methods in a computational model where the output is required to be an intrinsic description of the underlying set. We introduce a quantifier-elimination algorithm in this model. It turns out that our elimination algorithm has a doubly-exponential-time complexity in the worst case, when the complexity is measured in terms of syntactic parameters (number of polynomials and of quantifier alternations, dimension of the ambient space). We show that in our computational model, our algorithm is optimal, i.e., we prove a doublyexponential lower bound in the number of quantifier alternations of the input formula. Remarkably, we obtain simply-exponential complexity bounds on intrinsic geometric parameters of the input problem. Thus, our algorithm distinguishes between well-posed and ill-posed problems and can be inscribed in the new generation of algorithms which take also into account intrinsic, semantic invariants of the input in order to measure the complexity of the procedure. The Chapter 5 is the only chapter not related to complexity theory. Following the tradition of mathematical logic, we introduce new first-order languages for the elementary n-dimensional geometry and elementary n-dimensional affine geometry (n ≥ 2), based on extending the traditional languages FO(β, ≡) and FO(β), respectively, with new function symbols. Here, β stands for the betweenness relation and ≡ for the congruence relation. We show that the associated theories admit effective quantifier elimination.
Document URI:
Category: T1
Type: Theses and Dissertations
Appears in Collections:PhD theses
Research publications

Files in This Item:
File Description SizeFormat 
Thesis-RafaelGrimson.pdf1.22 MBAdobe PDFView/Open
Show full item record

Page view(s)

checked on Jul 4, 2022


checked on Jul 4, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.