List of books in computational geometry
Encyclopedia
This is a list of books in computational geometry
.
There are two major, largely nonoverlapping categories:
The conferences below, of broad scope, published many seminal papers in the domain.
Computational geometry
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 be part of computational...
.
There are two major, largely nonoverlapping categories:
- 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 as geometric modelingGeometric modelingGeometric modeling is a branch of applied mathematics and computational geometry that studies methods and algorithms for the mathematical description of shapes....
and computer-aided geometric design (CAGD), which deals with modelling of shapes of real-life objects in terms of curves and surfaces with algebraic representation.
General-purpose textbooks
-
- 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.
- The initial core of the book was M.I.Shamos' doctoral dissertation, which was suggested to turn into a book by a yet another pioneer in the field, Ronald GrahamRonald GrahamRonald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
. - The introduction covers the history of the field, basic data structures, and necessary notions from the theory of computationTheory of computationIn theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
and geometry. - The subsequent sections cover geometric searching (point locationPoint locationThe point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems , motion planning, and computer aided design ....
, range searchingRange searchingIn its most general form, the range searching problem consists of preprocessing a set S of objects, in order to determine which objects from S a query object, called a range, intersects...
), convex hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
computation, proximity-related problems (closest points, computation and applications of the Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
, Euclidean minimum spanning treeEuclidean minimum spanning treeThe Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...
, triangulationTriangulationIn trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...
s, etc.), geometric intersection problems, algorithms for sets of isothetic rectangles - The textbook provides an introduction to computation geometry from the point of view of practical applications. Starting with an introduction 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.
- 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".
Specialized textbooks and monographs
b-
- The monograph is a rather advanced exposition of problems and approaches in computational geometry focused on the role of hyperplane arrangements, 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.
- The books discusses parallel algorithms for basic problems in computational geometry in various models of parallel computation.
- 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 of convex hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
s, Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
s, and triangulationTriangulationIn trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...
s, proximity problemsProximity problemsProximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.A subset of these problems stated in terms of points only are sometimes referred to as closest point problems, although the term "closest point problem" is also used...
, and visibility problems. - Contents: Preface; 1. Background; 2. Point visibility; 3. Weak visibility and shortest paths; 4. L-R visibility and shortest paths; 5. Visibility graphVisibility graphIn computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them...
s; 6. Visibility graph theory; 7. Visibility and link paths; 8. Visibility and path queries - Contents:
- 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.
Monographs
The book is out of print. Its main chapters are:-
- Basic Concepts
- Boolean Operations on Boundary RepresentationBoundary representationIn solid modeling and computer-aided design, boundary representation—often abbreviated as B-rep or BREP—is a method for representing shapes using the limits...
- Robust and Error-Free Geometric Operations
- Representation of Curved Edges and Faces
- Surface Intersections
- Gröbner Bases Techniques
Other
- Thomas H. CormenThomas H. CormenThomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College and currently Chair of the Dartmouth College Department of Computer Science. Between 2004 and 2008 he directed...
, Charles E. LeisersonCharles E. LeisersonCharles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language...
, Ronald L. Rivest, and Clifford SteinClifford SteinClifford Stein, a computer scientist, is currently a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science. Stein is chair of the Industrial Engineering and Operations Research...
. Introduction to AlgorithmsIntroduction to AlgorithmsIntroduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities. It is also one of the most commonly cited references for algorithms in published papers, with over 4600...
, 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 UllmanJeffrey UllmanJeffrey David Ullman is a renowned computer scientist. His textbooks on compilers , theory of computation , data structures, and databases are regarded as standards in their fields.-Early life & Career:Ullman received a Bachelor of Science degree in Engineering...
, Computational Aspects of VLSI, Computer Science Press, 1984, ISBN 0-914894-95-1 — Chapter 9: "Algorithms for VLSI Design Tools" describes algorthms for polygon operations involved in electronic design automationElectronic design automationElectronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
(design rule checkingDesign rule checkingDesign Rule Checking or Check is the area of Electronic Design Automation that determines whether the physical layout of a particular chip layout satisfies a series of recommended parameters called Design Rules...
, circuit extraction, placement and routing). - D.T. LeeDer-Tsai LeeDer-Tsai Lee is a computer scientist, known for his work in computational geometry. For many years he was a professor at Northwestern University. He has been a distinguished research fellow of the Institute for Information Science at the Academia Sinica in Taipei, Taiwan since 1998. From 1998 to...
, 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. — This book has associated code repository with full Java implementations
Conferences
- Annual Symposium on Computational GeometrySymposium on Computational GeometryThe Annual Symposium on Computational Geometry is an academic conference in computational geometry. It was founded in 1985, and in most but not all of its years it has been sponsored by the Association for Computing Machinery's SIGACT and SIGGRAPH special interest groups.A 2010 assessment of...
(SoCG) - Canadian Conference on Computational Geometry (CCCG)
- Japanese Conference on Discrete and Computational Geometry (JCDCG)
The conferences below, of broad scope, published many seminal papers in the domain.
- ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Annual ACM Symposium on Theory of Computing (STOC)
- Annual IEEE Symposium on Foundations of Computer Science (FOCS)
- Annual Allerton Conference on Communications, Control and Computing (ACCC)
Paper collections
- "Combinatorial and Computational Geometry", eds. Jacob E. Goodman, János Pach, Emo Welzl (MSRI Publications – Volume 52), 2005, ISBN 0521848628.
- 32 papers, including surveys and research articles on geometric arrangements, polytopes, packing, covering, discrete convexity, geometric algorithms and their computational complexity, and the combinatorial complexity of geometric objects.
- "Surveys on Discrete and Computational Geometry: Twenty Years Later" ("Contemporary Mathematics" series), American Mathematical Society, 2008, ISBN 0821842390