| DATE: | Thursday, August 8th |
| TIME: | 1:00 PM - 2:00 PM |
| PLACE: | McConnell 320 |
| TITLE: | Algorithms for Bivariate Medians and a Fermat-Torricelli Problem for Lines |
| SPEAKER: | Greg Aloupis, School of Computer Science, McGill University |
Given a set S of n points in the plane, the Oja depth of a point X is the sum of the areas of all triangles formed by X and two elements of S. A point in the plane with minimum depth is an Oja median. We show how an Oja median may be computed in O(n log^3 n) time. In addition, we present an algorithm for computing the Fermat-Torricelli points of n lines in O(n) time. These points minimize the sum of weighted distances to the lines. Finally, we propose an algorithm which computes the simplicial median of S in O(n^4) time. This median is a point in the plane which is contained in the most triangles formed by elements of S.
This talk concerns research conducted recently by Greg Aloupis, Stefan
Langerman, Michael Soss and Godfried Toussaint.