The applet allows for interactive exploration of the algorithm. The algorithm does not itself solve the problem of finding the minimal width annulus for a given point set subject to the restriction of a fixed inner circle radius. Instead it allows the user to examine candidate solutions for a user-defined point set. (The fixed inner circle radius, 50 pixels, is not user-adjustable.) The best way to explain how to use this applet is to walk through a session and show pictorial examples.

To prevent the user from getting confused between screen shots of the applet and the applet itself, screen shots are clearly labelled as such and are drawn in a box. They are smaller than the applet and are right-justified. The applet is centered. Do not try clicking on the screen shots or pushing buttons in screen shots. (It will only frustrate you.) The applet is at the bottom.

Before the fun can begin, you must build a point set. Using your mouse, click at some random point on the applet screen. You should see a red dot. Points are depicted in red (just like in the example figures). This is the first point in the point set you are building. Randomly click on points on the applet screen a couple more times to build a small point set like in Figure 1.

Applet Screen Shot |

This applet introduces several geometric structures. If you were to look at all of them at once, there would probably be too many things on the screen and you might find it confusing. Thus this applet allows you to choose which structures you wish to see. By default points are visible, but no other structures are displayed. You can use the buttons on the bottom of the screen to toggle on/off the display of their associated structures. As a visual aid, each structure is displayed in its own color. Table 1 lists the different colors used.

Color | Structure |
---|---|

Black | Background |

Red | A point in the point set. The minimum width annulus should cover all the red points. Other points are not points in the point set and do not need to be covered. |

Gray | A Diametral Line |

White | An edge of the Farthest Point Voronoi Diagram |

Green | The Union of Open Discs (centered on the point set with the same radius as the inner circle) |

Yellow | The midpoint of a diametral line. Please note that this is probably not a point in the point set. The annulus need not cover these points. |

A vertice of the Farthest Point Voronoi Diagram | |

Magenta | An Intersection point betweent the Farthest Point Voronoi Diagram and the boundary of the Union of Open Discs |

Cyan | A vertice of the boundary of the Union of Open Discs |

Blue | A Candidate Annulus. Though technically the center point is not part of the annulus, this applet also displays the center point in blue. This is very similar to how the figures in the project display annuli. |

Now click the Diameters button. There should be a line connecting a diametral pair of points as in Figure 2. (Probably there will be only one diametral pair, but there could be more.)

Applet Screen Shot |

Now click the "Diameter Midpoints" button. A yellow dot should appear in the middle of all (probably one) the diametral lines, as in Figure 3. These yellow dot(s) are some of the candidate center points.

Applet Screen Shot |

Again click the "Diameter Midpoints" button and the "Diameters" button. This should toggle the display of those structures off. Now click the "FPVD" button. The display should be similar to Figure 4 which shows the Farthest Point Voronoi Diagram (of the red points).

Applet Screen Shot |

Now click the "FPVV" button. The display should show the vertices of the Farthest Point Voronoi Diagram as in Figure 5. (Actually you could have easily figured the vertices out from Figure 4, but this button makes them explicit.) These vertices are candidate center points.

Applet Screen Shot |

Again click the "FPVV" and "FPVD" buttons to make those structures invisible again. Now click the "Open Discs" button. The display should now show several overlapping green circles as in Figure 6. These are circles centered on the various points in the point set (the red points).

Applet Screen Shot |

Click again the "FPVD" diagram to make the Farthest Point Voronoi Diagram visible. Now Click the "Intersections" button. This shows you the intersections between the Farthest Point Voronoi Diagram and the boundary of the Union of Open Discs as in Figure 7. These are candidate points for the center.

Applet Screen Shot |

Click again the "Intersections" button to make those points invisible. Now click the "Disc Vertices" button to display the vertices of the boundary of the union of open discs as in Figure 9. These points are also candidate points for the center.

Applet Screen Shot |

Click the "Open Discs", "FPVD", and "Points" button to make those structures invisible. (The applet does allow you to make the point set invisible.) Now click the "Diameter Midpoints", "FPVV" and "Intersections" button. The display should consist only of the candidate center points as in Figure 9. While the applet calculates all of the candidate center points, it is possible that some candidates are outside the viewing range and thus not shown.

Applet Screen Shot |

Click the "Points" button to redisplay the point set. Now click the "Candidate" button to display a candidate annulus as in Figure 10. This is not necessarily (and probably not) the minimum width annulus, but it is built using one of the candidate center points.

Applet Screen Shot |

Now click the "Next" button to look at another candidate annulus as in Figure 111. Repeatedly clicking the "Next" button will cycle through the entire set of candidates. This applet does not find the minimum width annulus but instead leaves that as an exercise to the user.

After you have completed one cycle of the candidate annuli, pressing the "Next" button will not show a candidate annulus. This tells you that you have seen all the candidates. Pressing the "Next" button will restart the cycle and you can look at the candidates again.

Applet Screen Shot |

If you wish to know the coordinates of the plotted points, you can use the "Coords" button to turn on their display (as in Figure 12).

Applet Screen Shot |

At any time, you may add more points by clicking inside the applet. Alternatively, you may erase all your points by using the "Clear" button.

Now that you have taken the tutorial, you are ready to learn (and have fun) with the applet. Enjoy!