[Search][Subject Index][MathMap][Tour][Help!]

	ABOUT: [Introduction][History][Related areas][Subfields] POINTERS: [Texts][Software][Web links][Selected topics here] 68U: Computer graphics and computational geometry

Introduction

At present there is really nothing here regarding computer graphics per se; this is primarily focused on computational geometry.

In keeping with the general pattern of use of the Mathematics Subject Classifications, computational topics primarily focused on geometry are classified in sections 51: Geometry and 52: Convex Geometry and their subareas such as 52B: Polygons and polyhedra. This classification is intended for topics whose geometric aspects are fairly straightforward, but for which the main questions involve efficient, accurate computation.

Many geometric questions arise involving large sets of points (e.g. which of these points are closest together?) which are arguably combinatorics or statistics, but we have included them here.

History

Applications and related fields

Some problems (e.g. finding the best circle passing through some points) are considered Statistics.

Subfields

Parent field: 68U - Computing methodologies. But there is not yet a page for that; see its parent page, Computer Science.

Textbooks, reference works, and tutorials

Matousek, Jirí: "Mathematical snapshots from the computational geometry landscape", Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998). Doc. Math. 1998, Extra Vol. III, 365--375 (electronic). CMP1648170

Many of these questions arise in the USENET newsgroup comp.graphics.algorithms. Fortunately, that group has a nice FAQ file, the latest version of which may be found at the MIT USENET FAQ site. (The latest copy resides at rtfm.mit.edu:/usenet/comp.graphics.algorithms) There is also a moderated newsgroup comp.graphics.research .

Here is a list of books in computational geometry.

The book by de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried: "Computational geometry, Algorithms and applications", Springer-Verlag, Berlin, 1997. 365 pp. ISBN 3-540-61270-X, appears to be a nice textbook [not reviewed].

Book announcement: The Handbook Of Discrete And Computational Geometry, J. E. Goodman and J. O'Rourke, editors. (Intended for applications, not development of the theory.)

Software and tables

GAMS Computational geometry and Graphics software.

Computational Geometry package for Mathematica

LEDA is designed for computational geometry and combinatorics.

Other web sites with this focus

• The Geometry Literature Database (Computational geometry)
• Search Computational Geometry database, Max-Planck-Institut
• Geometry in Action
• Computational Geometry Pages
• Geometry Center software (which includes pointers to collections of codes such as Graphics Gems.
• UTK archives page.

Selected topics at this site

• Citations and pointers to computational geometry sources.
• Help wanted on circle-through-three-points problem.
• How to determine whether two ellipses intersect (or: solving quartics graphically)
• Fastest way to find nearest neighbors among finitely many points.
• Good way to find N nearest neighbors among finitely many points. (Clustering algorithms and k-d-trees: k points in d dimensions)
• Finding the furthest pair of points (in R^2): with citations
• Pointer: determining the intersection of a ray and a torus.
• Sample modelling of geometric problem: when do truncated cones intersect?
• Do two convex polyhedra intersect? (Use linear programming.)
• How to decide if you're inside a polyhedron?
• Drawing a circle on the computer.
• Drawing a circle without the trig functions
• Computing the envelope of a planar polygon (all points a given distance away).
• Decomposing a self-intersecting plane curve into simple curves
• Triangulating simple, nonconvex polygons
• Problems partitioning a polygon into triangles
• Optimal time for triangulating a polygon (n log n, or better!)
• Pointers for code for triangulating a polygon
• Triangulating polygons in R^3 -- when is it even possible?
• Citations: optimal convex decompositions of polygons
• Delaunay triangulation for non-convex regions
• Pointers to Delaunay triangulation codes
• Decomposing polyhedra into convex or tetrahedral pieces
• Calculating volumes of intersections of polyhedra.
• What is a Voronoi diagram and what is it good for?
• Best code for computing Voronoi diagrams
• Convex hull computations: summary and pointers
• Convex hull: Preparata and Hong algorithm
• Convex hull of points in the plane.
• Pointer to Quickhull (convex hull in R^N).
• Citation for convex hull and other geometric topics
• How to test for being in the interior of the convex hull?
• Pointer to implementations of bounding sphere calculations in R^n (especially: minimum bounding circle in the plane).
• Comparing complexity of convex hull, bounding sphere, and sorting problems.
• Finding the largest circle which can be inscribed in a polygon?
• Pointer to FAQ on Binary Space Partitioning (BSP) Trees
• Table Of Contents from "Graphic Gems" series (v. 1-5)
• Pointer to FAQ file for comp.graphics.algorithms
• How do you render hidden-line objects in 3D? (BSP trees)
• Might Peano curves be good for image compression?
• Can you get the sofa into the elevator and close the door?
• Triangulation of polyhedral domains
• Minimum bounding circle of a collection of planar points
• Minimum bounding sphere of a collection of points in space
• Is a given point inside the convex hull of a set of others?
• Polygon areas with Green's theorem (and little cancellation)
• Computing the intersection of two simplicial complexes in R^3