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 beezer@cs.mcgill.ca. , or sl@jeff.cs.mcgill.ca .

Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html