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

You may use the appletviewer, a tool included in Java SE Development Kit 8 (JDK 8), to view the demos.




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