In this paper we describe the first singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. We also describe algorithms for obtaining semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set. Singly exponential algorithms for computing the zero-th Betti number, and the Euler-Poincaré characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zero-th one.

Article A Helly-type theorem for hyperplane transversals to well-separated convex sets Share on Authors: Boris Aronov Polytechnic University, Brooklyn, NY Polytechnic University, Brooklyn, NYView Profile , Jacob E. Goodman City College, City University of New York, New York, NY City College, City University of New York, New York, NYView Profile , Richard Pollack Courant Institute of Mathematical Sciences, New York University, New York, NY Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile , Rephael Wenger The Ohio State University, Columbus, OH The Ohio State University, Columbus, OHView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 57–63https://doi.org/10.1145/336154.336178Online:01 May 2000Publication History 0citation233DownloadsMetricsTotal Citations0Total Downloads233Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given Q 2 R[X1 ; : : : ; Xk ] with deg(Q) d; we give an algorithm that outputs a semi-algebraic description for each of the semi-algebraically connected components of Z(Q) ae R k : The complexity of the algorithm as well as the size of the output are bounded by d O(k 3 ) : More generally, given any semi-algebraic set S defined by a quantifier-free formula involving a family of polynomials, P = fP1 ; : : : ; Psg ae R[X1 ; : : : ; Xk ] whose degrees are at most d; we give an algorithm that outputs a semi-algebraic description for each of the semialgebraically connected components of S: The complexity of the algorithm as well as the size of the output is bounded by s k+1 d O(k 3 ) : This improves the previously best known bound of (sd) k O(1) for this problem due to Canny, Grigor'ev, Vorobjov and Heintz, Roy and Solern`o [9, 14]. 1 Introduction Let R be a real closed field. A semi-algebraic set in R k is the set of points which satisfy a boolean combination of polynom...

We consider a family ofspolynomials, P = {P1, …,Ps}, inkvariables with coefficients in a real closed fieldR, each of degree at mostd, and an algebraic varietyVof real dimensionk′ which is defined as the zero set of a polynomialQof degree at mostd. The number of semi-algebraically connected components of all non-empty sign conditions on P overVis bounded bysk′(O(d))k. In this paper we present a new algorithm to compute a set of points meeting every semi-algebraically connected component of each non-empty sign condition of P overV. Its complexity issk′ + 1dO(k). This interpolates a sequence of results between the Ben-Or–Kozen–Reif algorithm which is the casek′ = 0, in one variable, and the Basu–Pollack–Roy algorithm which is the casek′ =k. It improves the results where the same problem was solved in timesk′ + 1dO(k′k).

We consider a semi-algebraic set S defined by s polynomials of degree d in k variables.We present a new algorithm for computing a semi-algebraic path in S comecting two points if they happen to lie in the same connected component of S.This algorithm, which works in time s ~tldo(~z) improves the complexity of the fastest algorithm solving this problem known to this date.

In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained.

We prove that a (k-1)-separated family of n compact convex sets in Rd can be met byk-transversals in at most O(d)d2((2k+1-2 / k) (n / k+1))k(d-k) or, for fixed k and d, O(nk(k+1)(d-k)) different order types. This is the first non-trivial bound for 1

In this paper we give a new algorithm for performing quantifier elimination from first order formulae over real closed fields. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this date. A new feature of our algorithm is that the role of the algebraic part (the dependence on the degrees of the input polynomials) and the combinatorial part (the dependence on the number of polynomials) are separated, making possible our improved complexity bound. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that we output, are independent of the number of input polynomials. As special cases of this algorithm, we obtain new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields. Using the theory developed in this paper, we also give an improved bound on the radius of a ball centered at the origin, which is guaranteed to intersect every connected component of the sign partition induced by a family of polynomials. We also use our methods to obtain algorithms for solving certain decision problems in real and complex geometry which improves the complexity of the currently known algorithms for these problems.>

Article Free Access Share on There is a universal topological plane Authors: Jacob E. Goodman View Profile , Richard Pollack View Profile , Rephael Wenger View Profile , Tudor Zamfirescu View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992Pages 171–176https://doi.org/10.1145/142675.142714Published:01 July 1992Publication History 0citation272DownloadsMetricsTotal Citations0Total Downloads272Last 12 Months25Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

We show that the maximum combinatorial complexity of the space of hyperplane transversals to a family of n separated and strictly convex sets in Rd is Θ(n⌊d/2⌋), which generalizes results of Edelsbrunner and Sharir in the plane. As a key step in the argument, we show that the space of hyperplanes tangent to κ ≤ d separated and strictly convex sets in Rd is a topological (d - κ)-sphere.

A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.>

We will prove that a finite family B = {B1, B2, …, Bn} of connected compact sets in Rd has a hyperplane transversal if and only if for some k there exists a set of points P = {P1, P2, …, Pn} (i.e. a k-dimensional labeling of the family) which spans Rk and every k + 2 sets of B are met by a k-flat consistent with the order type of P. This is a common generalization of theorems of Hadwiger, Katchalski, Goodman-Pollack and Wenger.

We give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. The lower bound is achieved by the construction of a widely dispersed “rigid” configuration which is then modified to one in general position by recent techniques of Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou on the solution of simultaneous inequalities. This provides a sharp answer to a question first posed by Chazelle.

Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union of n regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected Riemann surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan arcs in the upper halfplane starting and ending on the x-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), where α(n) is the extremely slowly growing functional inverse of Ackermann's function.

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n - 4 by n - 2 grid and provide an Ο(n) space, Ο(n log n) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n + (1 - ο(1)) √n which settles a problem of Mohar.

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time Ο (n2), where n is the number of sides of P. We also give an Ο(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.

We present efficient algorithms for the following geometric problems: (i) Preprocessing of a 2-D polyhedral terrain so as to support fast ray shooting queries from a fixed point. (ii) Determining whether two disjoint interlocking simple polygons can be separated from one another by a sequence of translations. (iii) Determining whether a given convex polygon can be translated and rotated so as to fit into another given polygonal region. (iv) Motion planning for a convex polygon in the plane amidst polygonal barriers. All our algorithms make use of Davenport Schinzel sequences and on some generalizations of them; these sequences are a powerful combinatorial tool applicable in contexts which involve the calculation of the pointwise maximum or minimum of a collection of functions.

Article Free Access Share on Modeling planar configurations Authors: Jacob E. Goodman City College, CUNY City College, CUNYView Profile , Richard Pollack Courant Institute, NW Courant Institute, NWView Profile Authors Info & Claims SCG '85: Proceedings of the first annual symposium on Computational geometryJune 1985Pages 121–124https://doi.org/10.1145/323233.323250Published:01 June 1985Publication History 0citation169DownloadsMetricsTotal Citations0Total Downloads169Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We introduce a process called geometric sorting, which can be applied to an arbitrary configuration of points in d space, and which encodes in compact form the order properties of the configuration, just as the arrangement of a set of numbers in size place encodes its order properties. We give an algorithm for carrying out this sorting procedure in time $O(n^d \log n)$, which generalizes the optimum sorting time of $O(n\log n)$ for the linear case; In addition, we give an efficient algorithm for determining whether two randomly numbered configurations in $\mathbb{R}^d $ have the same order type, using a distinguished family of orderings of each. Finally, we indicate how this new concept of sorting can be applied to problems in pattern recognition, stereochemistry, and cluster analysis.