Here are a few notes and instructions for using the applet:
CLICK HERE TO LOAD THE APPLET
- First of all, Netscape 4 or above is highly recommended, otherwise
the animation looks awful (points dissapear and such...).
- The usage is fairly simple: just input a set of points with the
mouse, select an algorithm, and watch it run.
- The speed of the animation can be adjusted using the menu on the
top right (if the speed is set to "Instant", the applet will simply
highlight the closest pair, and report the distance without any
- The yellow bar shows the current status, and also displays the
distance (in pixels) between the closest pair of points once
the algorithm has terminated.
- The yellow bar reports the number of comparisons between points
done by the algorithm in order to find the closest pair. Note that
the plane sweep algorithm uses fewer comparisons on the average
(can you decipher why?).
- The algorithm is color-coded as follows:
- The current set under scrutiny is highlighted in blue.
- The strip about the median within this set is highlighted
- The bounding box within that strip is highlighted in yellow
(note that if either the strip or the bounding box contain the
entire set under scrutiny, the whole set will be highlighted).
- Each time two points are compared, they are colored red and joined
by a red line.
- For the Divide-and-Conquer algorithm:
- Any sets for which a local minimum has been computed
will be shown in gray. You will see these sets merge toghether
as the algorithm progresses.
- Every time a new local closest pair is discovered,
they are joined by a flashing green line.
- The current median is drawn as a blue vertical line
- For the Plane Sweep algorithm:
- Every time a new closest pair is encountered, the
corresponding points are joined by a flashing green line.
- The current closest pair are joined by a solid green line.
link leads to another applet that demonstrates the divide-and-conquer
algorithm. Although the animation is fancier than mine, the applet
doesn't show the bounding box which gives the algorithm its O(nlogn)
Sam Bakhtiar SANJABI
Last modified: Tue Apr 25 08:33:21 EDT 2000