- List of books in computational geometry
This is a

**list of books in**There are two major, largely nonoverlapping categories:computational geometry .

*Combinatorial computational geometry, which deals with collections of discrete objects or defined in discrete terms: points, lines, polygons, polytopes, etc., and algorithms of discrete/combinatorial character are used

*Numerical computational geometry, also known asgeometric modeling andcomputer-aided geometric design (CAGD), which deals with modelling of shapes of real-life objects in terms of curves and surfaces with algebraic representation.**Combinatorial computational geometry****Textbooks and monographs*** cite book

author =Franco P. Preparata andMichael Ian Shamos | title = Computational Geometry - An Introduction | publisher =Springer-Verlag | year = 1985 | id = 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6

*:The book is the first comprehensive monograph on the level of a graduate textbook to systematically cover the fundamental aspects of the emerging discipline of computational geometry. It is written by founders of the field and the first edition covered all major developments in the preceding 10 years. In the aspect of comprehensiveness it was preceded only by the 1984 survey paper, Lee, D, T., Preparata, F. P. : "Computational geometry - a survey". "IEEE Trans. on Computers ". Vol. 33, No. 12, pp. 1072-1101 (1984). It is focused on two-dimensional problems, but also has digressions into higher dimensions. [*MR|0805539, MR|1004870*] [*Zbl|0575.68037, Zbl|0575.68059*]

*:The initial core of the book was M.I.Shamos' doctoral disserttion, which was suggested to turn into a book by a yet another pioneer in the field,Ronald Graham .

*:The introduction covers the history of the field, basic data structures, and necessary notions from thetheory of computation and geometry.

*:The subsequent sections covergeometric searching (point location ,range searching ),convex hull computation, proximity-related problems (closest points , computation and applications of theVoronoi diagram ,Euclidean minimum spanning tree ,triangulation s, etc.),geometric intersection problems , algorithms for sets ofisothetic rectangle s

* cite book

author =Herbert Edelsbrunner |year = 1987 | title = Algorithms in Combinatorial Geometry | publisher =Springer-Verlag | id = ISBN 0-89791-517-8

*:The monograph is a rather advanced exposition of problems and approaches in computational geometry focused on the role ofhyperplane arrangement s, which are shown to constitute a basic underlying combinatorial-geometric structure in certain areas of the field. The primary target audience are active theoretical researchers in the field, rather than application developers. Unlike most of books in computational geometry focussed on 2- and 3-dimensional problems (where most applications of computational geometry are), the book aims to treat its subject in the general multi-dimensional setting. [*A review of Edelsbrunner's book in Zbl|0634.52001*]

* cite book

author =Mark de Berg ,Otfried Cheong ,Marc van Kreveld , andMark Overmars | year = 2008 | title = Computational Geometry | publisher =Springer-Verlag | edition = 3rd revised edition | id = ISBN 3-540-77973-6, 1st edition (1987): ISBN 3-540-61270-X

*:The textbook provides an introduction to computation geometry from the point of view of practical applications. Starting with an introducion chapter, each of the 15 remaining ones formulates a real application problem, formulates an underlying geometrical problem, and discusses techniques of computational geometry useful for its solution, with algorithms provided in pseudocode. The book treats mostly 2- and 3-dimensional geometry. The goal of the book is to provide a comprehensive introduction into methods and approached, rather than the cutting edge of the research in the field: the presented algorithms provide transparent and reasonably efficient solutions based on fundamental "building blocks" of computational geometry. [*Reviews in Zbl|0877.68001 (1st ed.), Zbl|0939.68134 (2nd ed.)*] [*[*]*http://www.cs.uu.nl/geobook/ About the book by de Berg, van Kreveld, Overmars, and Schwarzkopf*]

*:The book consists of the following chapters (which provide both solutions for the topic of the title and its appilications): "Computational Geometry (Introduction)" "Line Segment Intersection", "Polygon Triangulation", "Linear Programming", "Orthogonal Range Searching", "Point Location", "Voronoi Diagrams", "Arrangements and Duality", "Delaunay Triangulations", "More Geometric Data Structures", "Convex Hulls", "Binary Space Partitions", "Robot Motion Planning", "Quadtrees", "Visibility Graphs", "Simplex Range Searching".

* cite book

author =Jean-Daniel Boissonnat ,Mariette Yvinec | year = 1998 | title = Algorithmic Geometry | publisher =Cambridge University Press | edition = Translation of a 1995 French edition | id = ISBN 0-521-56529-4

* cite book

author =Kurt Mehlhorn | year = 1984 | title = Data Structures and Efficient Algorithms 3: Multi-dimensional Searching and Computational Geometry | publisher =Springer-Verlag | edition = | id =

* cite book

author =Ketan Mulmuley | year = 1994 | title = Computational Geometry: An Introduction Through Randomized Algorithms| publisher =Prentice-Hall | edition = | id = ISBN 0-13-336363-5

* cite book

author = Joseph O'Rourke | year = 1998 | title = Computational Geometry in C| publisher =Cambridge University Press | edition = 2nd edition| id = ISBN 0-521-64976-5

* cite book

author =Janos Pach andPankaj K. Agarwal | year = 1995 | title = Combinatorial Geometry| publisher =John Wiley and Sons | edition = | id = ISBN 0-471-58890-3

* cite book

author =Micha Sharir andPankaj K. Agarwal | year = 1995 | title = Davenport-Schinzel Sequences and Their Geometric Applications| publisher =Cambridge University Press | edition = | id = ISBN 0-521-47025-0

* cite book

author =Kurt Mehlhorn andStefan Naeher | year = 1999 | title = LEDA, A Platform for Combinatorial and Geometric Computing| publisher =Cambridge University Press | edition = | id = ISBN 0-521-56329-1

* cite book

author =Jörg-Rudiger Sack and Jorge Urrutia| year = 1998| title = Handbook for Computational Geometry | publisher =North-Holland | edition = | id = 1st edition: ISBN 0-444-82537-1, 2nd edition: 1-584-88301-4

* cite book

author =Selim G. Akl andKelly A. Lyons | year = 1993 | title = Parallel Computational Geometry | publisher =Prentice-Hall | edition = | id = ISBN 0-13-652017-0

*: The books discusses parallel algorithms for basic problems in computational geometry in various models ofparallel computation . [*A review of the Akl-Lyons book in MR|1211180 (94c:68192)*]

* cite book

author = Joseph O'Rourke| year = 1987 | title = Art Gallery Theorems and Algorithms | publisher =Oxford University Press | edition = | id =

* cite book

author =Hanan Samet | year = 1990 | title = The Design and Analysis of Spatial Data Structures | publisher =Addison-Wesley | edition = | id =

* cite book

author = Clara I. Grima and Alberto Márquez | year = 1990 | title = Computational Geometry on Surfaces: Performing Computational Geometry on the Cylinder, the Sphere, the Torus, and the Cone | publisher =Kluwer Academic Publishers | edition = | id = 1402002025

*:The book shows how classical problems of computational geometry and algorithms for their solutions may be adapted or redesigned to work on surfaces other than plane. After defining notations and ways of positioning on these surfaces, the book considers the problems of the construction ofconvex hull s,Voronoi diagram s, andtriangulation s,proximity problems , andvisibility problems .

*cite book

first=Subir Kumar

last=Ghosh

year=2007

title=Visibility Algorithms in the Plane

publisher=Cambridge University Press

isbn=0521875749

*:Contents: Preface; 1. Background; 2.Point visibility ; 3.Weak visibility andshortest path s; 4. L-R visibility and shortest paths; 5.Visibility graph s; 6. Visibility graph theory; 7. Visibility andlink path s; 8. Visibility and path queries [*[*]*http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521875745 "Visibility Algorithms in the Plane"*] , from the Cambridge University Press catalogue

*cite book

author = Giri Narasimhan, Michiel Smid

title = Geometric Spanner Networks

publisher =Cambridge University Press

year = 2007

isbn=0521815134

*:Contents: [*[*]*http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521815134 "Geometric Spanner Networks"*] , from the Cambridge University Press catalogue

**Part I. Introduction: 1. Introduction; 2. Algorithms and graphs; 3. The algebraic computation-tree model;

**Part II. Spanners Based on Simplical Cones: 4. Spanners based on the Q-graph; 5. Cones in higher dimensional space and Q-graphs; 6. Geometric analysis: the gap property; 7. The gap-greedy algorithm; 8. Enumerating distances using spanners of bounded degree;

**Part III. The Well Separated Pair Decomposition and its Applications: 9. The well-separated pair decomposition; 10. Applications of well-separated pairs; 11. The Dumbbell theorem; 12. Shortcutting trees and spanners with low spanner diameter; 13. Approximating the stretch factor of Euclidean graphs;

**Part IV. The Path Greedy Algorithm: 14. Geometric analysis: the leapfrog property; 15. The path-greedy algorithm; Part V. Further Results and Applications: 16. The distance range hierarchy; 17. Approximating shortest paths in spanners; 18. Fault-tolerant spanners; 19. Designing approximation algorithms with spanners; 20. Further results and open problems.**References*** cite book

author =Jacob E.Goodman and Joseph O'Rourke (editors)| year = 1997, 2004| title = Handbook for Computational Geometry | publisher =North-Holland | edition = | id = 1st edition: ISBN 0-8493-8524-5, 2nd edition: ISBN 1-584-88301-4

*:In its organization, the book resembles the classical handbook in algorithms, "Introduction to Algorithms ", in its comprehensiveness, only restricted to discrete and computational geometry,computational topology , as well as a broad range of their applications. The second edition expands the book by half, with 14 chapters added and old chapters brought up to date. Its 65 chapters (in over 1,500 pages) are written by a large team of active researchers in the field. [*A review of the "Handbook for Computational Geometry" in "*]Geombinatorics ", January 2005.

*

*:The handbook contains survey chapters in classical and new studies in geometric algorithms: hyperplane arrangements, Voronoi diagrams, geometric and spatial data structures, polygon decomposition, randomized algorithms, derandomization, parallel computational geometry (deterministic and randomized), visibility, Art Gallery and Illumination Problems,closest point problems , link distance problems, similarity of geometric objects,Davenport-Schinzel sequence s,spanning tree s and spanners for geometric graphs, robustness and numerical issues for geometric algorithms, animation, and graph drawing.

*:In addition, the book surveys applications of geometric algorithms in such areas asgeographic information system s, geometric shortest path and network optimization and mesh generation.**Numerical computational geometry (geometric modelling, computer-aided geometric design)****Monographs*** cite book|author =

I. D. Faux andMichael J. Pratt | year = 1980 | title = Computational Geometry for Design and Manufacture (Mathematics & Its Applications)

publisher =Prentice Hall | edition = | id = ISBN 0-470-27069-1

*

* cite book|author =Jean-Daniel Boissonnat andMonique Teillaud | year = 2006 | title = Effective Computational Geometry for Curves and Surfaces

publisher =Springer Verlag | edition =Mathematics and Visualization Series | id = ISBN 3-540-33258-9

* cite book|author =Gerald Farin | year = 1988

title = Curves and Surfaces for Computer Aided Geometric Design

publisher =Academic Press | edition = | id = ISBN 0-12-249050-9

* cite book|author =Richard H. Bartels ,John C Beatty , andBrian A. Barsky | year = 1987

title = Splines for Use in Computer Graphics and Geometric Modeling

publisher =Morgan Kaufmann | edition = | id = ISBN 0-934613-27-3

* cite book|author =Christoph M. Hoffmann | year = 1989

title = Geometric and Solid Modeling: An Introduction

publisher =Morgan Kaufmann | edition = | isbn = 1558600671 | url = http://www.cs.purdue.edu/homes/cmh/distribution/books/geo.html The book is out of print. Its main chapters are:

**Basic Concepts

**Boolean Operations on Boundary Representation

**Robust and Error-Free Geometric Operations

**Representation of Curved Edges and Faces

**Surface Intersections

**Gröbner Bases Techniques**Other***

Thomas H. Cormen ,Charles E. Leiserson ,Ronald L. Rivest , andClifford Stein . "Introduction to Algorithms ", Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. — This book has a chapter on geometric algorithms.

*Frank Nielsen . "Visual Computing: Graphics, Vision, and Geometry", Charles River Media, 2005. ISBN 1584504277 — This book combines graphics, vision and geometric computing and targets advanced undergraduates and professionals in game development and graphics. Includes some concise C++ code for common tasks.

*Jeffrey Ullman , "Computational Aspects ofVLSI ", Computer Science Press, 1984, ISBN 0-914894-95-1 — Chapter 9: "Algotithms for VLSI Design Tools" describes algorthms forpolygon operations involved inelectronic design automation (design rule checking ,circuit extraction ,placement and routing ).

*D.T.Lee, Franco P. Preparata, "Computational Geometry - A Survey",IEEE Trans. Computers , vol 33 no. 12, 1984, 1072-1101. (Errata: IEEE Tr. C. vol.34, no.6, 1985) Although not a book, this 30-page paper is of historical interest, because it was the first comprehensive coverage, the 1984 snapshot of the emerging discipline, with 354-item bibliography.**Conferences***Annnual Symposium on Computational Geometry

*Canadian Conference on Computational Geometry ( [*http://www.cccg.ca/ CCCG*] )

*Japanese Conference on Discrete and Computational Geometry ( [*http://wotan.liu.edu/docis/dbl/jcdcgj/index.html JCDCG*] )

*The conferences below, of broad scope, published many seminal papers in the domain

**Annual ACM Symposium on Theory of Computing ( [*http://sigact.acm.org/stoc/ STOC*] )

**Annual IEEE Symposium on Foundations of Computer Science ( [*http://focs06.cs.princeton.edu/ FOCS*] )

**Annual Allerton Conference on Communications, Control and Computing ( [*http://www.csl.uiuc.edu/allerton/ ACCC*] )**References**

* [*http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ Computational Geometry Pages*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Computational geometry**— is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to… … Wikipedia**List of mathematics articles (L)**— NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… … Wikipedia**Geometry**— (Greek γεωμετρία ; geo = earth, metria = measure) is a part of mathematics concerned with questions of size, shape, and relative position of figures and with properties of space. Geometry is one of the oldest sciences. Initially a body of… … Wikipedia**List of academic disciplines**— An academic discipline, or field of study, is a branch of knowledge that is taught and researched at the college or university level. Disciplines are defined (in part), and recognized by the academic journals in which research is published, and… … Wikipedia**List of unsolved problems in mathematics**— This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory … Wikipedia**Computational chemistry**— is a branch of chemistry that uses principles of computer science to assist in solving chemical problems. It uses the results of theoretical chemistry, incorporated into efficient computer programs, to calculate the structures and properties of… … Wikipedia**Computational photography**— Computational imaging refers to any image formation method that involves a digital computer. Computational photography refers broadly to computational imaging techniques that enhance or extend the capabilities of digital photography. The output… … Wikipedia**List of important publications in mathematics**— One of the oldest surviving fragments of Euclid s Elements, found at Oxyrhynchus and dated to circa AD 100. The diagram accompanies Book II, Proposition 5.[1] This is a list of important publications in mathematics, organized by field. Some… … Wikipedia**List of Stuyvesant High School people**— This article lists notable people associated with Stuyvesant High School in New York City, New York, organized into rough professional areas and listed in order by their graduating class. MathematicsStuyvesant High School has produced a steady… … Wikipedia**List of multiple discoveries**— Main article: Multiple discovery Copernicus … Wikipedia