McGill University - School of Computer Science

Algorithms Seminar Fall 2001

Everybody is welcome!

DATE: Wednesday, November 21th
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: The expected number of visibility events amongst uniformly distributed unit balls is linear.
SPEAKER: Hyeon-Suk Na, INRIA-Lorraine, Nancy, France

A fundamental step in any rendering algorithm is to determine whether two points are mutually visible. Rendering algorithms are notoriously slow and in fact, they spend a majority of their time on visibility computations. One approach to speeding up rendering is to store global visibility information in a data structure which can then be efficiently queried and the visibility complex has been proposed for this purpose. However, one problem with these data structures which prevents their application in practice is their potentially enormous size; the size of the visibility complex in the worst case is $\Theta(n^4)$, which is prohibitive even for relatively modest scenes.

In this talk, we show that the expected number of visibility events is linear amongst uniformly distributed unit balls which provides a linear bound on the expected size of visibility complex.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.