Speaker: Todd Phillips Time: Wednesday 12-1pm Place: NSH 1507 Title: Data Structures for Cellular Decompositions Abstract: In many applications of comptutational geometry, we seek to store and manipulate a complex geometric collection that has been decomposed into primitive geometric objects (cells). Common examples include the storage of meshes, scenes, arrangements, or embedded planar graphs. Good data structures must efficiently support localized operations for exploring adjacency and containment between these cells. In general, such decompositions may have very complicated neighborhoods and connectedness that can lead to computational topology problems. We will explore state of the art data structures, and we will see how a group theoretic approach to the problem can yield very elegant solutions. We will also present some recent contributions from both algebraic and data structures viewpoints.