Campus Event Calendar
Event Entry
New for: D3
What and Who
Computing the diameter of a 3-d point set deterministically (SIG-CG)
Edgar Ramos
SIG Meeting
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 27 August 99
13:30
60 Minutes
46
07
Saarbrücken
Abstract
Given a set of n points in R^3, the problem is to find a
pair farther from each other than any other pair. An optimal
randomized algorithm by Clarkson and Shor (1989) has so far
resisted derandomization with optimal O(n log n) running time.
I'll present a new optimal randomized algorithm that can be
easily derandomized, using now standard techniques, while
achieving optimal running time.
Contact
Edgar A. Ramos
--email hidden
passcode not visible
logged in users only