McGill University - School of Computer Science

Algorithms Seminar Summer 2001

Everybody is welcome!

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.