1-Disc Cover problem with obstacles



Left-click inside the red square to add a point.
Left-click on an existing point to delete it.
Right-click to draw a polygon in counter clockwise order.
Right-click the polygon's starting point or double right-click in order to close it.
Use the buttons to clear all points, delete the last polygon, or read/write the data from/to a file.

The applet shows the center and radius of the smallest disc that covers all the points and whose center is not inside one of the polygons (the red circle). In paranthesis are the differences between this disc and the smallest possible disc that covers the points, with no restrictions on its center (the cyan circle).

Download the 1DC package - 1DC.tar.gz.