Considering the large volume of sequence data that many computational biology applications must deal with, proper organization of the data to facilitate fast access is important to achieve desirable run-times.

The 'bisection width' of a graph is defined as the minumum number of edges that need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large.

This talk will provide a brief introduction to the art gallery problem, which was first posed to Chvátal by Victor Klee in 1973.

This will be a talk on the proof of NP hardness of the Art Gallery Problem (which was described by Pritam last week). Approximation algorithms for the terrain guarding problem will also be described.

Last time around we saw some interesting and non-intuitive behaviour of volumes and surfaces in high dimensions.