The Hong Kong University of Science and Technology
Department of Computer Science


PhD Qualifying examination


"Reporting Pairwise Segment Intersections"

By Mr. Antoine Emile Vigneron

Abstract:

Reporting pairwise segment intersections is a fundamental
problem in computational geometry. It can be formulated
as follows:
let $E$ be a set of line or curve segments in the plane,
find the pairs of segments in $E^2$ that intersect.
Since the first output sensitive algorithm published in
1979 by Bentley and Ottmann, it has been
extensively studied and now optimal algorithms have been
designed under several computation models and for many
variants of the problem. We will survey on the general
case and the so called red--blue case, then we will look
into the I/O efficient and the low degree algorithms for
reporting pairwise intersections.


Date:                   Tuesday, 27 February 2001

Time:                   4:30 p.m. onwards
        
Venue:                  Room 1504
			Lift 25-26
                       

Chairman:               Dr. Fangzhen Lin

Committee Members:      Dr. Siu-Wing Cheng (Supervisor)
                        Dr. Rudolf Fleischer
                        Dr. Mordecai Golin
			Dr. Sunil Arya


**** ALL are Welcome ****