Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Guibas Talk on Computational Geometry
Posted:
Jan 25, 2005 9:53 PM


Dr. Leonidas Guibas, one of the leading researchers in Computational Geometry, is visiting the University of Minnesota and the Geometry Center on November 15 and 16. He is going to give a talk on campus during his visit: Date: Monday November 15 Time: 2:30 pm Place: 108 Mechanical Engineering Building Precolloquium reception is at 2:00pm in the 5th floor lounge of the EE/CS Dept. Abstract:
RANDOMIZED ALGORITHMS IN COMPUTATIONAL GEOMETRY
Leonidas J. Guibas
Stanford University
The major intellectual contribution of the area of algorithms to Computer Science as a whole over the past ten years has been the introduction of the use of randomization as a fundamental tool of algorithm design. Randomization not only yields some of the asymptotically most efficient algorithms  it does so through algorithms that are amazingly simple and therefore eminently implementable and practical. In this talk I will explore a number of different paradigms for developing efficient algorithms in computational geometry using randomization. Among others, I will illustrate the techniques of partitioning by random sampling, randomized incremental construcions, and randomized reweighing.



