PST Demo - How to use this applet

Creating a pointset

To add points, click the mouse on the background of the applet. A blue point will appear where the mouse button was released. To move any existing point, click the mouse over the point and drag to the new location and release. To delete points, hold the mouse over a point and hit the "Backspace" or "Delete" key on the keyboard.

Random points may also be added by clicking on the gray "Random pts" button near the bottom of the applet.

Loading and saving a pointset

Alternatively, a pointset may be loaded. Type the filename of the pointset in the "Load/Save pointset:" text field at the bottom of the applet and press the "Load" button. A listing of existing pointsets is available.

Any pointset you create can also be saved. Type the filename to save the pointset as in the "Load/Save pointset:" text field at the bottom of the applet and press the "Save" button. Caution: Saving a pointset will erase any exiting pointset by that name.

Performing range queries

By clicking on the "Create tree" button near the bottom of the applet, a priority search tree is formed from the points in the plane. Once the tree is computed, the applet will draw edges from each node to its children. Left children have black incoming edges and right children have red incoming edges.

A 3-sided range query box will appear on the graph once the tree is computed. To perform range queries, resize the dark gray box from the sides or the corners. Whenever the mouse is released, a range query is performed and the display will be updated. This range query is equivalent to the "enumerate" procedure that McCreight describes.

Points that were successfully found within the range are colored magenta for success. Points visited by the enumeration query but not within the range are colored cyan for failure. All edges traversed by the query are drawn with thicker strokes.

Visualizing the median line

The median line of every point can be visualized by toggling the "Visualize median" checkbox near the bottom of the applet.

Michael J. Radwin, mjr@acm.org

Last modified: Tue Mar 4 09:34:12 EST 1997