awesome-computational-geometry

Computational geometry references

A curated collection of resources and references for computational geometry

A curated list of awesome computational geometry visualizations, frameworks, and resources

GitHub
70 stars
4 watching
3 forks
last commit: about 2 years ago
Linked from 1 awesome list

algorithmalgorithmsawesomeawesome-listcomputer-sciencegeometrymathematics

Awesome Computational Geometry / 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
Point/Line Duality A type of mathematical duality frequently used in computational geometry algorithms
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

Awesome Computational Geometry / 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)

Awesome Computational Geometry / 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)
Computing in Euclidean Geometry A collection of surveys and exploratory articles about recent developments in the field of computational Euclidean geometry by Ding-Zhu Du and Frank Hwang (1995)

Awesome Computational Geometry / Libraries
CGAL A software project that provides easy access to efficient and reliable geometric algorithms in the form of a C++ library. This website also has explanations of many of these algorithms
Wykobi An extremely efficient, robust, and simple to use C++ 2D/3D oriented computational geometry library
geometry3Sharp 1,720 5 months ago Open-Source, Boost-licensed C# library for geometric computing
Computational Geometry Software Libraries UIUC's large collection and library of geometric software by Jeff Erickson
The Stony Brook Algorithm Repository A repository of algorithms based on
Geometric Tools A library of source code for computing in the fields of mathematics, graphics, image analysis, and physics that includes some computational geometry algorithms
GeoLib A fast and efficient computational geometry library available in C++, C# and Java
hull.js 587 14 days ago JavaScript library that builds the convex hull of a set of points
S2 Geometry Library 2,326 14 days ago A package for manipulating geometric shapes. Unlike many geometry libraries, S2 is primarily designed to work with spherical geometry, i.e., shapes drawn on a sphere rather than on a planar 2D map. This makes it especially suitable for working with geographic data
Computational Geometry Unity Library 1,254 5 months ago A library of computational geometry algorithms for Unity

Awesome Computational Geometry / Conferences / Strictly Computational Geometry
Symposium on Computational Geometry An annual symposium
The Canadian Conference on Computational Geometry An annual international event for the dissemination of new results in the fields of computational and combinatorial geometry. The conference is usually held in a Canadian city sometime in mid-August
Japan Conference on Discrete and Computational Geometry, Graphs, and Games A conference held annually since 1997, except for 2008

Awesome Computational Geometry / Conferences / Broader
Symposium on Discrete Algorithms ACM-SIAM, held annually
Annual ACM Symposium on Theory of Computing STOC covers all areas of research within Algorithms and Computation Theory
IEEE Symposium on Foundations of Computer Science The flagship conference sponsored by the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF) and covers a broad range of theoretical computer science
Annual Allerton Conference on Communications, Control and Computing Draws some of the brightest minds from industry, academia, and government to discuss innovation in the fields of communication, control, and computing

Awesome Computational Geometry / Journals
arXiv Recent submissions to arXiv about computational geometry
Elsevier A forum for research in theoretical and applied aspects of computational geometry
Journal of Computational Geometry An international open access journal devoted to publishing original research of the highest quality in all aspects of computational geometry

Awesome Computational Geometry / Competitive Programming
HackerEarth A set of articles on computational geometry
TopCoder A set of articles on computational geometry
HackerRank A set of programming problems using computational geometry
GeeksforGeeks Implementations and explanations for a large number of commonly asked questions and common topics in geometric algorithms

Awesome Computational Geometry / Courses / Open Courses
MIT OCW A course taught by Nicholas Patrikalakis and Takashi Maekawa in 2013
Udemy A course about implementing computational geometry algorithms in C++
edX A course in computational geometry
Brilliant Practice problems for basic concepts in computational geometry

Awesome Computational Geometry / Courses / University Courses
Brown University A course taught by Roberto Tamassia in 2005
Washington University in St. Louis A course taught by Tao Ju in 2017
The University of Maryland A course taught by Dave Mount in 2002
UC Santa Barbara A course taught by Subhash Suri in 2021
UIUC A course taught by Jeff Erickson in 2022
UC Berkeley A course taught by Jonathan Shewchuk in 2019
Tufts A course taught by Diane Souvaine in 2022
KIT A course taught by Tamara Mchedlidze and Chih-Hung Liu in 2018

Awesome Computational Geometry / Miscellaneous
The Open Problems Project A project aimed to record important open problems in computational geometry and related fields
Wolfram Documentation for computational geometry algorithms implemented in the Wolfram language
Matlab Documentation for computational geometry algorithms implemented in the Matlab

Backlinks from these awesome lists:

More related projects: