Some project and survey suggestions

You may find a webpage on Geometry in Action helpful.

These geometry pages are a very good general resource, and include links to bibliographies and search pages for them.

The report of the taskforce on application challenges for computational geometry application may be helpful.

Surveys of the current literature for these areas might be of interest.

geometric problems in statistics,: including robust statistics: statistical estimators that are not lead astray by a small number of input values that are wildly wrong; possibly also spatial statistics.
surface reconstruction:: given a set of points in 3d, find a "reasonable" surface containing those points
kinetic computational geometry: maintaining geometric information as input data moves
external memory computational geometry: handling geometric problems that have input data sets so large that they don't fit in main memory.
geometric problems in data mining and cluster analysis
approximation of geometric objects
geometric problems in approximating functions and in scattered data interpolation
geometric problems in geographic information systems
visibility problems: given a set of opaque objects and a viewpoint, which can be seen? Can that information be updated for a moving viewpoint?
many-body simulation

For some of these problems, I have particular algorithms in mind; for others, I can only point you to the literature for ideas.

For any of these, there are may be existing codes that might be adopted for use.

Java implementations of almost any of the algorithms described in class would be of interest. Also:

given a planar subdivision, or a polyhedron in 3d, subdivide it into convex pieces; this is a hard problem, but the 2d case is conceivable.
"crusts" are a surface reconstruction technique (see above) using Voronoi diagrams; implement them in 2d or 3d.
given a convex polytope, approximate it with a polytope having fewer vertices. Proposed algorithms do so within a constant factor of best possible.
given a set of points, compute their smallest enclosing sphere or ellipsoid, or other smallest enclosing... Known algorithms can do this in linear time.
given two convex polytopes, compute the distance between them. this can be done in linear time.
given a set of points in d dimensions, compute the vertices of their convex hull;
implement and experiment with "natural neighbor interpolation" methods, a technique for scattered data interpolation that uses Voronoi diagrams.
implement an algorithm for the "all-nearest-neighbors" problem: given a set of sites (points), find, for every site, the nearest other site. The algorithm uses quadtrees in a straightforward way.

The following collections of geometric software may be helpful or inspiring.

Ken Clarkson
August 1997