COS 226 Programming Assignment

Where to Build a School (or Detonate a Bomb)

Applications. The smallest enclosing circle problem has numerous applications. For example, consider the placement of a new school to service a number of students. If we model the students as points in the plane, the smallest enclosing circle specifies where to build the school: placing the school at the circle's center minimizes the distance between the school and the furthest student. Alternatively, if we view the points as military targets, the minimum enclosing circle specifies where to drop a bomb to destroy the targets, and its radius tell us how much explosive is required.

Geometric properties. Given a set of points in the plane, the smallest enclosing circle is uniquely defined. Moreover, the smallest enclosing circle is characterized by two or three of the points, which lie on its circumference.

Specifically, the smallest enclosing circle is one of the following:

• A circle whose circumference contains 2 of the N points and the points are antipodal (180 degrees apart). If the two points are (x_i, y_i) and (x_j, y_j), then the circle has center and radius:
  

• A circle whose circumference contains 3 of the N points. If the three points are (x_i, y_i), (x_j, y_j), and (x_k, y_k), then the circle has center and radius:
  

  and the determinant of a 3-by-3 matrix is defined as follows:

  

Geometric data types. To organize your program, implement a data type Circle for circles in the plane and a data type Point for points in the plane. You must implement the following API, but you are free to add additional methods as appropriate.

public class Point {
   public Point(double x, double y)  // construct a point (x, y)
   public void draw()                // draw point to standard draw
   public String toString()          // string representation
}

public class Circle {
   public Circle(Point center, double radius)    // circle with given center and radius
   public Circle(Point p1, Point p2)             // circle with given 2 points on diameter
   public Circle(Point p1, Point p2, Point p3)   // circle with given 3 points on circumference
   public boolean contains(Point p)              // does circle contain the point on circumference or interior?
   public void draw()                            // draw circle to standard draw
   public String toString()                      // string representation
}

Brute force. Write a client Brute that examines all pairs and all triples of points, checks which of the corresponding circles encloses all N points, and outputs the smallest such circle. Organize your program to implement the following API.

public class Brute {
   public Brute(Point[] points)      // constructor takes array of points
   public Circle sec()               // return the smallest enclosing circle
}

An efficient algorithm. Your next task is to design and implement a client Fast that solves the smallest enclosing circle problem more efficiently. We leave this as an open-ended challenge. There are many ideas that you can try; you are encouraged to brainstorm on your own and discuss ideas with with the course staff. You should strive for an algorithm that is efficient, both in practice and in theory. Organize your program to implement the following API.

public class Fast {
   public Fast(Point[] points)       // constructor takes array of points
   public Circle sec()               // return the smallest enclosing circle
}

Input and output. The data files consist of an integer N, followed by N pairs of real numbers (x, y). The points will all lie in the unit circle: (x² + y² ≤ 1).

% more input6.txt       % more input7.txt
6                       7
  0.000    0.987          0.375   -0.605
 -0.350    0.462          0.375    0.695
 -0.296    0.160          0.511    0.127
  0.345    0.034         -0.481    0.238
  0.239   -0.680         -0.845   -0.190
  0.647    0.326         -0.067   -0.462
                          0.389   -0.258

Include a main() method in Brute.java and Fast.java that reads the points from standard input, prints the smallest enclosing circle to standard output, and draws the points and the circle on standard drawing. Scale the coordinate system so that coordinates between -1 and +1 fit in the standard drawing window.

% java Brute < input6.txt
(0.1195, 0.15349999999999997) 0.8420228619224065

% java Fast < input6.txt
(0.1195, 0.15349999999999997) 0.8420228619224065

% java Brute < input7.txt
(-0.08447745901639338, 0.044999999999999964) 0.7960022206904712

% java Fast < input7.txt
(-0.08447745901639338, 0.044999999999999964) 0.7960022206904712

Analysis. Estimate (using tilde notation) the average-case running time (in seconds) of your two programs as a function of the number of points N (where the points are generated uniformly in the unit circle). Provide empirical evidence to justify your hypotheses. Also, give the order-of-growth of the worst-case running time of your two program as a function of N?

Deliverables. Submit Brute.java, Fast.java, Point.java, and Circle.java, along with any other helper files needed to run your program (excluding those in adt.jar and stdlib.jar). Also submit a readme.txt and answer all questions.