Union of Rectangles

Given a collection of Range Minimum Queries

What were the high and low values of the S&P 500 in the past day, week, month, year, or decade. More generally, given two calendar days, what were the high and low values of the market between the two given days. Since the cases are symmetric, we are interested in an algorithm for supporting such range minimum queries. Given an array Art Gallerys

A local museum is exhibiting a large collection of priceless art. Naturally they would not want the art to be stolen so they would like to set up a number of cameras to observe the room. Unfortunately with artists being creative types the room is not a rectangle which can be observed with a single camera. Suppose the room is decribed by a simple but non-convex polygon. We wish to place cameras at the vertices of the polygon such that the entire interior of the polygon is visible by the cameras. Suppose the each camera can see arbitrarily far in a straight line as long as no walls obstruct the view. Furthermore assume the cameras have a viewing angle of 360 degrees. How many cameras are needed to cover a polygonal art gallery with Line Segment Intersection

Given a collection of Image classification with limited memory

A common task in image processing is to identify the number, size, and shape of connected regions in the image that have the same (or similar) intensity values. For example, a traffic camera might detect cars as darker blobs against a lighter higway background. An infared camera might identify animals as brighter spots against a dark backround. Suppose I am given a grid of pixels where each pixel has an integer intensity value. I would like to assign a unique label to each connected component in the image where a connected component is a connected region in the image where all pixels in the component have the same intensity value and for which I can go from any pixel in the connected component to any other pixel in the component via a path that is completely within the component. One easy solution is to run a breadth first search on each unvisited pixel to identify its connected compenent. This works great if I can load the entire image into memory. Suppose I add the constraint that only a constant number of rows fit into memory. Design an algorithm that still solves the problem, but reduces the number of times I need to load a row into memory.
Google Maps Spatial Queries

Google maps and other map search engines allow users to search using text queries that describe geographic locations. Another way to search for objects would be to allow searches to be describe by a geographic box, circle, or in the most general case, an arbitrary two dimensional simply connected planar region. How would you design a data structure to store and query two dimensional point data using such query regions. It suffices to focus on bounded rectangular axis-aligned queries. Can you design a structure to support queries and updates? Analyze the space and runtime complexity of your approach.