Image approximation to efficiently support direction queries

The representation and processing of spatial queries is important in numerous application domains in the areas of computer-aided design, multimedia databases, spatial and geographic applications. A sample query type in these applications is to find objects that satisfy a specific direction relation with respect to a given object. Due to the large size of these databases and the complexity of geometric algorithms, appropriate indexing techniques and object approximations are crucial. The problem is that the relationships between object approximations are usually a superset of the actual relationships between their corresponding objects, resulting in a number of false hits. A challenge, hence, is to reduce the number of false hits in order to decrease the number of times we invoke the complex geometric algorithms on the actual representations of the objects. Two different image shape approximation techniques minimum bounding circles (MBC) and minimum bounding rectangles (MBR) are compared. MBC was shown to be preferred over minimum bounding rectangles (MBR) for our application. The support of direction queries using spatial data structures based on the minimum bounding circle approximation (MBC) will be described. By identifying special cases in MBC relations, extra filtering steps are proposed to reduce the number of false hits, and hence further enhance the direction relation query response time.