Richard Pollack

STOC Conference 2005 Conference Paper

Computing the first Betti number and the connected components of semi-algebraic sets

• Saugata Basu
• Richard Pollack
• Marie-Françoise Roy

STOC Conference 1996 Conference Paper

Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract)

• Saugata Basu
• Richard Pollack
• Marie-Françoise Roy

FOCS Conference 1994 Conference Paper

On the Combinatorial and Algebraic Complexity of Quantifier Elimination

• Saugata Basu
• Richard Pollack
• Marie-Françoise Roy

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. >

TCS Journal 1992 Journal Article

Arrangements of curves in the plane—topology, combinatorics, and algorithms

• Herbert Edelsbrunner
• Leonidas Guibas
• János Pach
• Richard Pollack
• Raimund Seidel
• Micha Sharir

Arrangements of curves in the plane are fundamental to many problems in computational and combinatorial geometry (e. g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of Edelsbrunner (1986) and Chazelle (1985) to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves) and an application of that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.

FOCS Conference 1990 Conference Paper

Counting and Cutting Cycles of Lines and Rods in Space

• Bernard Chazelle
• Herbert Edelsbrunner
• Leonidas J. Guibas
• Richard Pollack
• Raimund Seidel
• Micha Sharir
• Jack Snoeyink

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. >

STOC Conference 1989 Conference Paper

Coordinate Representation of Order Types Requires Exponential Storage

• Jacob E. Goodman
• Richard Pollack
• Bernd Sturmfels

STOC Conference 1988 Conference Paper

Small Sets Supporting Fáry Embeddings of Planar Graphs

• Hubert de Fraysseix
• János Pach
• Richard Pollack

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 2 n - 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.

FOCS Conference 1986 Conference Paper

Geometric Applications of Davenport-Schinzel Sequences

• Micha Sharir
• Richard Cole 0001
• Klara Kedem
• Daniel Leven
• Richard Pollack
• Shmuel Sifrony

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.