Home / research areas / CG
Computational Geometry
Originally, Computational Geometry was defined as the study of algorithms for solving geometric problems. Since then it has broadened its scope, and now means the study of geometric problems from a computational point of view, including also computational convexity, computational topology, and questions involving the combinatorial complexity of arrangements and polyhedra.
(Some) Problems:
- Art Gallery;
- Convex Hull;
- Graph Drawing;
- Voronoy Diagrams;
- Geometric Graphs;
- Triangulation.
References:
- J. O’Rourke. Art gallery theorems and algorithms. Oxford University Press, Inc., New York, NY, USA, 1987.
- J. O’Rourke, E. D. Demaine, and J. S. B. Mitchell. Open problems project, 2013.
- F. P. Preparata, and M. I. Shamos. Computational Geometry: An Introduction (Monographs in Computer Science). Monographs in Computer Science (Springer-Verlag, New York, 1985), ISBN 3540961313 (1993).
- J. E. Goodman, and J. O’Rourke, eds. Handbook of discrete and computational geometry. CRC press, 2010.