Spatial Index Demos

Brought to you by Frantisek Brabec (brabec at and Hanan Samet (hjs at

These applets are based on algorithms published in the following books:

Click here for the table of contents and a 20% discount coupon

A short course on some of the algorithms and data structures used in these applets was held at UC Berkeley on March 29-31, 1999.

If you are interested in these spatial index demos, you could be also interested in our most recently developed software - SAND Internet Browser. SAND is a spatial data browser and spatial database engine with Java front-end.

Window and Range search operations were replaced by more general Overlap Search. Overlap Search finds all the objects (e.g., rectangles) in the current data structure that intersect the query object (e.g., a path). The particular type of intersection can be specified by setting the additional conditions.

More query object types for which the nearest neighbor algorithm can be run were added. Now you can rank objects by their distance from point, rectangle, polygon, path, and sector. Also the Within query was added that finds all the objects within a given distance from a query object.

Required software

All the applets on this page use JDK 1.4 features. These are supported by the latest versions of both Mozilla Firefox (1.5 or newer) and MS Internet Explorer (7.0 or newer) browsers. If you cannot upgrade your browser, click here for the older version of the point structures demo, here for the older version of the rectangle structures demo and here for the older version of the line structures demo.

To use the original Sun's implementation of JDK in your browser, you can download and install Javasoft's Java Plug-in.




Region Quadtrees


For an explanation of the implemented algorithms as well as their visualization and animation, click on one of the following links:

Other Features