5 Closest Pair: Interactive Java 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 animation).
• 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 in pink.
  • 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.
  • This 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) performance.