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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.