The project is to pursue ongoing investigations into core areas of computational geometry, in particular, cell decomposition, mesh generation, multidimensional searching, and geometric optimization. The research will span the spectrum from the theoretical (e.g., lower bounds, geometric sampling techniques, derandomization) to the practical (implementation and distribution of geometric software). Progress in the field has been hampered by the difficulty in testing out new geometric ideas on a computer. As a result, experimentation has often taken a backseat to theoretical research. Essential to this project is the building of software tools (e.g., algorithm animation, visual debugging, test data generation) that facilitate and encourage the use of experimentation. ***
