## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, July 01, 2004, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Csaba Dávid Tóth (U. of California at Santa Barbara)

## Binary space partitions of orthogonal subdivisions

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size O(n d+1/3), for all d>2, and that such a partition can be computed in time O(K log n), where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space that requires a BSP of size Ω(nf(d)), where f(d) converges to (1+ √5)/2 as d goes to infinity.

(Joint work with John Hershberger and Subhash Suri)

Information for students and suggested topics for student talks