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 Pre-colloquium reception is at 2:00pm in the 5th floor lounge of the EE/CS Dept. Abstract:
RANDOMIZED ALGORITHMS IN COMPUTATIONAL GEOMETRY
Leonidas J. Guibas
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 re-weighing.