Orthogonal Range Reporting in One and Two Dimensions on the RAM

PhD Qualifying Examination


Title: "Orthogonal Range Reporting in One and Two Dimensions on the RAM"

by

Mr. Ge LUO


Abstract:

We consider the problem of orthogonal range reporting on the RAM. Given a
set S of n points in d dimensions, we want to build a data structure such
that given any orthogonal range R, we can report all points in S \cap R
efficiently. This problem can be easily solved in the comparison model
with a query time of O(log n+k), where k is the output size, but on the
RAM it is possible to achieve much lower running times with a rich set of
techniques.

In this survey, we will review a series of data structures for one and
two-dimensional orthogonal range reporting on the RAM in both the static
and dynamic case. We will first introduce several important techniques in
this field. Then we will survey some representative results. At the end,
we will introduce some related lower bounds for this problem.


Date:                   Tuesday, 18 October 2011

Time:                   2:00pm - 4:00pm

Venue:                  Room 3408
                         lifts 17/18

Committee Members:	Dr. Ke Yi (Supervisor)
                         Prof. Mordecai Golin (Chairperson)
 			Dr. Sunil Arya
 			Prof. Siu-Wing Cheng


**** ALL are Welcome ****