McGill University - School of Computer Science

Algorithms Seminar 2002

Everybody is welcome!

DATE: Friday, September 13th
TIME: 5:00 PM - 6:00 PM
PLACE: McConnell 320
TITLE: Cost-Optimal Trees for Ray Shooting
SPEAKER: Herve Bronnimann, Polytechnic University, New York

In this talk, I introduce a cost measure on space decompositions for a given set of objects (points, segments in 2D, triangles in 3D). This cost measure was introduced in a paper by Aronov, Chang, Chiang, and myself at SoCG'02, to predict the cost of ray shooting. In a CCCG'02 paper, we proposed a construction of quadtrees which yields cost O(M), where M is the infimum of the cost measure on all quadtrees, for either points or segments in 2D.

In this talk, I will examine the case of octrees, and more generally d-dimensional trees with points and (d-1)-dimensional simplices, with respect to their cost measure. I will present a construction of quadtrees and octrees which yields cost O(M), where M is the infimum of the cost measure on all trees, for points or for (d-1)-simplices.

Sometimes, a balance condition is important. (Informally speaking, balanced trees ensures that neighboring leaves have similar size.) I will also state and analyze a rebalancing algorithm for trees in arbitrary dimension, and show that rebalancing does not affect the cost by more than a constant multiplicative factor, for both points and (d-1)-simplices.

This is joint work with Marc Glisse. The CCCG paper was joint work with Marc, and with David Wood.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at , or .
Web Address: