| 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.