Computational Geometry Books

[Shelly Takacs]

Iwant to solve geometry problems in online programming contests. But whenever I read them, I just find too difficult. Please suggest some books and resources which I can study computational geometry.

Discrete geometry is a relatively new development in pure mathematics, while computational geometry is an emerging area in applications-driven computer science. Their intermingling has yielded exciting advances in recent years, yet what has been lacking until now is an undergraduate textbook that bridges the gap between the two. Discrete and Computational Geometry offers a comprehensive yet accessible introduction to this cutting-edge frontier of mathematics and computer science.

This book covers traditional topics such as convex hulls, triangulations, and Voronoi diagrams, as well as more recent subjects like pseudotriangulations, curve reconstruction, and locked chains. It also touches on more advanced material, including Dehn invariants, associahedra, quasigeodesics, Morse theory, and the recent resolution of the Poincar conjecture. Connections to real-world applications are made throughout, and algorithms are presented independently of any programming language. This richly illustrated textbook also features numerous exercises and unsolved problems.

The book is a collection of some of the research presented at the workshop of the same name held in May 2003 at Rutgers University. The workshop brought together researchers from two different communities: statisticians and specialists in computational geometry. The main idea unifying these two research areas turned out to be the notion of data depth, which is an important notion both in statistics and in the study of efficiency of algorithms used in computational geometry. Many of the articles in the book lay down the foundations for further collaboration and interdisciplinary research.

This book clearly satisfies the goals of the editors: it contains state-of-the-art contributions on data depth that may be of interest to statisticians, mathematicians, computer scientists, and computational geometers. Connections between the different research fields are well exposed. This will certainly stimulate further interdisciplinary research.

The opening article by R.-H. Wang gives a nice survey of various aspects of computational geometry, many of which are discussed in detail in the volume. Topics of the other articles include problems of optimal triangulation, splines, data interpolation, problems of curve and surface design, problems of shape control, quantum teleportation, and more.

Geometric shapes belong to our every-day life, and modeling and optimization of such forms determine biological and industrial success. Similar to the digital revolution in image processing, which turned digital cameras and online video downloads into consumer products, nowadays we encounter a strong industrial need and scientific research on geometry processing technologies for 3D shapes.

Several disciplines are involved, many with their origins in mathematics, revived with computational emphasis within computer science, and motivated by applications in the sciences and engineering. Just to mention one example, the renewed interest in discrete differential geometry is motivated by the need for a theoretical foundation for geometry processing algorithms, which cannot be found in classical differential geometry.

This book series is devoted to new developments in geometry and computation and its applications. It provides a scientific resource library for education, research, and industry. The series constitutes a platform for publication of the latest research in mathematics and computer science on topics in this field.

Discrete geometry has contributed significantly to the growth of discrete mathematics in recent years. This has been fueled partly by the advent of powerful computers and by the recent explosion of activity in the relatively young field of computational geometry. This synthesis between discrete and computational geometry lies at the heart of this Handbook.

A growing list of application fields includes combinatorial optimization, computer-aided design, computer graphics, crystallography, data analysis, error-correcting codes, geographic information systems, motion planning, operations research, pattern recognition, robotics, solid modeling, and tomography.

Finite point configurations. Packing and covering. Tilings. Helly-type theorems and geometric transversals. Pseudoline arrangements. Oriented matroids.Lattice points and lattice polytopes. Low-distortion embeddings of finite metric spaces. Geometry and topology of polygonal linkages. Geometric graph theory. Euclidean Ramsey theory. Discrete aspects of stochastic geometry. Geometric discrepancy theory and uniform distribution. Polyominoes. Basic properties of convex polytopes. Subdivisions and triangulations of polytopes. Face numbers of polytopes and complexes. Symmetry of polytopes and polyhedra. Polytope skeletons and paths. Polyhedral maps.Topological methods in discrete geometry.Random simplicial complexes. Computational topology of graphs on surfaces. Persistent homology. High-dimensional topological data analysis. Convex hull computations. Voronoi diagrams and Delaunay triangulations. Arrangements.Triangulations and mesh generation. Polygons.Shortest paths and networks. Proximity algorithms. Visibility. Geometric reconstruction problems. Curve and surface reconstruction. Computational convexity. Computational and quantitative real algebraic geometry.Point location. Collision and proximity queries. Range searching. Ray shooting and lines in space. Geometric intersection. Nearest neighbors in high-dimensional spaces.Randomizaton and derandomization. Robust geometric computation. Parallel algorithms in geometry. Epsilon-nets and epsilon-approximations Coresets and sketches. Linear programming. Algorithmic motion planning. Robotics. Computer graphics. Modeling motion. Pattern recognition. Graph drawing.Splines and geometric modeling. Solid modeling. Computation of robust statistics: Depth, median, and related measures. Geographic information systems.Geometric applications of the Grassmann-Cayley algebra. Rigidity of symmetric frameworks. Global rigidity. Crystals, periodic and aperiodic..Applications to structural molecular biology. Geometry and topology of genomics. Software. Two computational geometry libraries: LEDA and CGAL

"Discrete and computational geometry is a thriving field, and the collective knowledge represented in this third edition of the Handbook is evidence of this. Twenty years have passed since the publication of the first edition [Handbook of discrete and compu-tational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997; MR1730156], and since then, the area has seen a tremendous growth due in part to the influence of both the first and second editions [Handbook of discrete and computational geometry, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004; MR2082993] of the Handbook. The new edition can be expected to serve a similar purpose for future generations of researchers and practitioners.

The third edition of the Handbook has been substantially revised. The addition of almost 400 pages has resulted in a volume of well over 1900 pages. Fifty-eight out of the sixty-five chapters of the second edition have been updated (sometimes with a slightly revised title), many of them by the original authors, others in collaboration with new co-authors. Ten new chapters have been added, for an overall count of sixty-eight chapters.

The new version remains an invaluable resource for anyone interested in discrete and computational geometry and in related areas, including specialists and non-specialists. The Handbook continues to be an attractive one-stop reference book."

The aim of this volume is to give an introduction and overview to differential topology, differential geometry and computational geometry with an emphasis on some interconnections between these three domains of mathematics. The chapters give the background required to begin research in these fields or at their interfaces. They introduce new research domains and both old and new conjectures in these different subjects show some interaction between other sciences close to mathematics. Topics discussed are; the basis of differential topology and combinatorial topology, the link between differential geometry and topology, Riemanian geometry (Levi-Civita connextion, curvature tensor, geodesic, completeness and curvature tensor), characteristic classes (to associate every fibre bundle with isomorphic fiber bundles), the link between differential geometry and the geometry of non smooth objects, computational geometry and concrete applications such as structural geology and graphism.

LinkedIn and 3rd parties use essential and non-essential cookies to provide, secure, analyze and improve our Services, and to show you relevant ads (including professional and job ads) on and off LinkedIn. Learn more in our Cookie Policy.

3a8082e126