Logo - springer
Slogan - springer

Mathematics - Geometry & Topology | Discrete and Computational Geometry - The Goodman-Pollack Festschrift

Discrete and Computational Geometry

The Goodman-Pollack Festschrift

With contributions by numerous experts

Series: Algorithms and Combinatorics, Vol. 25

Aronov, B., Basu, S., Pach, J., Sharir, M. (Eds.)

2003, XII, 853 p. In 2 volumes, not available separately.

Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-3-642-55566-4

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Hardcover version

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-3-540-00371-7

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-3-642-62442-1

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

This is an impressive collection of original research papers in discrete and computational geometry, contributed by many leading researchers in these fields, as a tribute to Jacob E. Goodman and Richard Pollack, two of the `founding fathers' of the area, on the occasion of their 2/3 x 100 birthdays. The topics covered by the 41 papers provide professionals and graduate students with a comprehensive presentation of the state of the art in most aspects of discrete and computational geometry, including geometric algorithms, arrangements, geometric graph theory and quantitative and algorithmic real algebraic geometry, with important connections to algebraic geometry, convexity, polyhedral combinatorics, and the theory of packing, covering, and tiling.

The book will serve as an invaluable source of reference in this discipline, and an indispensible component of the library of anyone working in the above areas.

Content Level » Research

Keywords » Combinatorial Geometry - Computational Geometry - Discrete Geometry - Graph - Graph theory - Node - Real Algebraic Geometry - Sim - algorithms - complexity - programming

Related subjects » Geometry & Topology - Probability Theory and Stochastic Processes - Theoretical Computer Science

Table of contents 

On the Complexity of Many Faces in Arrangements of Pseudo-Segments and of Circles.- Polyhedral Cones of Magic Cubes and Squares.- of the Polygons.- Computing the Hausdorff Distance of Geometric Patterns and Shapes.- A Sum of Squares Theorem for Visibility Complexes and Applications.- On the Reflexivity of Point Sets.- Geometric Permutations of Large Families of Translates.- Integer Points in Rotating Convex Bodies.- Complex Matroids ¨C Phirotopes and Their Realizations in Rank.- Covering the Sphere by Equal Spherical Balls.- Lower Bounds for High Dimensional Nearest Neighbor Searchand Related Problems.- A Tur´an-type Extremal Theory of Convex Geometric Graphs.- Relaxation.- A Lower Bound on the Complexity of Approximate Nearest-NeighborSearching on the Hamming.- Detecting Undersampling in Surface Reconstruction.- A Survey of the Hadwiger-Debrunner (p, q)-problem.- Surface Reconstruction by Wrapping Finite Sets in Space.- Infeasibility of Systems of Halfspaces.- Complete Combinatorial Generation of Small Point Configurations and Hyperplane.- Relative Closure and the Complexity of Pfaffian Elimination.- Are Your Polyhedra the Same as My Polyhedra.- Some Algorithms Arising in the Proof of the Kepler Conjecture.- The Minimal Number of Triangles Needed to Span a Polygon Embedded in Rd.- Jacobi Decomposition and Eigenvalues of Symmetric Matrices.- Discrete Geometry on Red and Blue Points in the Plane¨C A Survey ¨C.- Configurations with Rational Angles and Trigonometric DiophantineEquations.- Reconstructing Sets From Interpoint Distances.- Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio.- Colorings and Homomorphisms of Minor Closed Classes.- Conflict-free Colorings.- New Complexity Bounds for Cylindrical Decompositions of Sub-Pfaffian Sets.- Note on the Chromatic Number of the Space.- Expansive Motions and the Polytope of Pointed Pseudo-Triangulations.- Some Recent Quantitative and Algorithmic Results in Real Algebraic Geometry.- A Discrete Isoperimetric Inequality and Its Application to Sphere Packings.- On the Number of Maximal Regular Simplices Determined by n Points in Rd.- Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem.- Quantizing Using Lattice Intersections.- Note on a Generalization of Roth’s Theorem.- Arrangements, Equivariant Maps and Partitions of Measures by k-Fans.- Qualitative Infinite Version of Erd?s’ Problem About Empty Polygons.

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Geometry.