McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.
DATE: Thursday, November 12th, 1998
TIME: 11:30-12:30
PLACE: McConnell 320
TITLE: Degree versus time-complexity in geometric algorithms
SPEAKER: Jean-Daniel Boissonat, INRIA Sophia-Antipolis
We consider whether restricted sets of geometric primitives support efficient algorithms for line and curve segment intersection problems in the plane. Our restrictions are based on the notion of algebraic degree as a way to guide the search for efficient algorithms that can be implemented in more realistic computational models than the Real RAM. We introduce two models of computation aimed at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of algebraic expressions of some degree, and the second model (exact arithmetic) assumes the exact computation of the value of such (bounded-degree) expressions.

Suppose that n (pseudo-)segments have k intersections at which they cross. We show that intersection algorithms for monotone curves that use only above/below tests for endpoints and intersection tests must take at least Omega(n sqrt{k}) time.

We then identify the characteristic geometric property enabling the correct report of all intersections by plane sweeps. Verification of this property involves only comparisons and above/below tests (which are of degree 2 for line segments) but its straightforward implementation appears highly inefficient. We then present algorithmic variants of the Bentley-Ottmann algorithm that have a lower degree and achieve the same performance as the original algorithm. For line segments, we give a variant of Balaban's algorithm which is close to optimal and has degree 2. We also consider red/blue line and curve segment intersection, in which the segments are colored red and blue so that there are no red/red or blue/ blue crossings. We present a time-optimal optimal O(n log n + k) algorithm which is also optimal with respect to the degree.

Joint work with Franco Preparata (Brown) and Jack Snoeyink (British Columbia)

This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.