PhD Qualifying Examination


"Exteranl memory computational geometry"

By Mr. Yan Zhang


Abstract:

In recent years more and more attention has been paid to the "I/O
bottleneck"  resulting from running algorithms on massive data sets that
can not fit into internal memory.  This has led to the development of
"External Memory" algorithms that are designed to minimize disk I/O time,
i.e., page faults during their running.  One active subarea is the design
of such algorithms for Computational Geometry Problems.  In this talk we
survey various external memory computational geometry algorithms and
discuss general paradigms for designing them. The problems include convex
hull, triangulation, interval management, planar point location, 2D range
searching, orthogonal line segment intersection, etc. The applications of
these algorithms include spatial and temporal database, VLSI design, GIS
system, statistics, VR system, computer graphics, etc.


Date:     		Monday, 25 August 2003

Time:                   1:00p.m.-3:00p.m.

Venue:                  Room 2304
			lifts 17-18

Committee Members:      	Dr. Mordecai Golin (Supervisor)
                        Prof. Derick Wood (Chairman)
			Dr. Sunil Arya
			Dr. Rudolf Fleischer


**** ALL are Welcome ****