Awesome Computational Geometry
A curated list of awesome computational geometry visualizations, libraries, and resources.
Computational geometry is a topic in computer science that focuses on solving problems in geometry. Applications of computational geometry include computer-aided design, robotics, GIS systems, and computer vision.
Contents
- Algorithm Visualizations
- Books
- Notes
- Libraries
- Conferences
- Strictly Computational Geometry
- Broader
- Journals
- Competitive Programming
- Courses
- Open Courses
- University Courses
- Miscellaneous
Algorithm Visualizations
- Convex Hull - The convex hull of a shape is the smallest convex set that contains it.
- Convex Hull Algorithms - A website with visualizations of many convex hull algorithms, including gift wrapping, Graham's scan, quickhull, divide and conquer, monotone chain, and Chan's algorithm.
- Chan's Algorithm - An optimal output-sensitive algorithm to compute the convex hull of a set of points in 2 or 3 dimensions.
- Kirkpatrick's Point location - A data structure and method for point location with O(n) space and O(log n) query time using triangulation.
- Voronoi Diagrams - A partition of a plane into regions close to a given set of points.
- Fortune's Algorithm - A sweep line algorithm for generating the Voronoi diagram in O(n log n) time and O(n) space.
- k-d tree - A method of partitioning k-dimensional space in an efficient way for searches like nearest neighbors.
- Configuration Space - The space of possible configurations of an object like a robot.
- CGViz: Computational Geometry Interactive Visualizations (GitHub) - CGViz is a FOSS web app for step-by-step visualizations of many algorithms, designed for exploration, teaching, and creating exportable visuals.
Books
- Computational Geometry: Algorithms and Applications - A textbook by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars (2008).
- Computational Geometry in C - A popular introduction to the design and implementation of geometry algorithms arising in areas such as computer graphics, robotics, and engineering design by Joseph O'Rourke (1998).
- Computational Geometry: An Introduction - An introductory textbook by Franco P. Preparata and Michael I. Shamos (1993).
- Algorithmic Geometry - A textbook by Jean-Daniel Boissonnat, Mariette Yvinec, and Herve Bronniman (1998).
- Discrete and Computational Geometry - A comprehensive yet accessible introduction to the intermingling of discrete geometry, a relatively new development in pure mathematics, and computational geometry, an emerging area in applications-driven computer science by Satyan L. Devadoss and Joseph O'Rourke (2011).
- Interactive Computational Geometry - A taxonomic approach - An interactive introduction to some of the fundamental algorithms of computational geometry with Mathematica by Jim Arlow (2014).
Notes
- Lecture Notes - Lecture notes from CMSC 754 Computational Geometry at the University of Maryland by David Mount (2002).
- Handbook of Discrete and Computational Geometry - A handbook by Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth (2017).
- Handbook of Computational Geometry - An overview of key concepts and results in computational geometry by J. R. Sack, and J. Urrutia (1998).