Klee's Measure Problem Made Easy

Speaker:        Professor Timothy Chan
                University of Waterloo
                        &
                Visiting Professor
                HKUST

Title:          "Klee's Measure Problem Made Easy"

Date:           Monday, 21 October 2013

Time:           4:00pm - 5:00pm

Venue:          Lecture Theatre F (near lifts 25/26), HKUST

Abstract:

In a well-known problem in computational geometry called "Klee's measure
problem", we want to compute the volume of the union of n boxes in d
dimensions, where the boxes are axis-parallel and may overlap. For
example, for d=2, we want the area of the union of n rectangles.  Finding
the best algorithm for this easy-to-state problem turns out to be open
even for d=3. In this talk, I will review the history of the problem and
describe a recent development: a new algorithm that runs in O(n^{d/2})
time for any d>=3, based on divide-and-conquer but with a simple twist.


**********************
Biography:

Timothy Chan is a Professor of Computer Science at the University of
Waterloo, and is currently a Visiting Professor at HKUST.  He received his
B.A. from Rice University in 1992 and his Ph.D. from the University of
British Columbia in 1995.  His research interests are in algorithms and
data structures, and especially, computational geometry. He was a winner
of the NSERC Doctoral Prize and was an invited speaker for several
conferences, including the ACM-SIAM Symposium on Discrete Algorithms. He
has served on many program committees and is on the editorial board of
five journals, including Discrete & Computational Geometry, Algorithmica,
and ACM Transactions on Algorithms.