Geombinatoric Aspects of Processing Large Images and Large Spatial Databases

Computer processing can drastically improve the quality of an image and the reliability and accuracy of a spatial database. A large image (database) does not easily fit into the computer memory, so we process it by downloading pieces of the image. Each downloading takes a lot of time, so, to speed up the entire processing, we must use as few pieces as possible. Many algorithms for processing images and spatial databases consist of comparing the value at a certain spatial location with values at nearby locations. For such algorithms, we must select (possibly overlapping) sub-images in such a way that for each point, its neighborhood (of given radius) belongs to a single sub-image. We reformulate the corresponding optimization problem in geometric terms, and use this reformulation to provide some information about the solution. Namely, for images, the optimal sub-images should be bounded by straight lines or circular arcs; for non-homogeneous spatial databases, we deduce an explicit expression for the curvature of the boundaries in terms of the data density in different points