Assignment 2 --- Due Monday, March 5, 2007


Theory
  1. Suppose that some non-simple polygon is drawn in the plane, and the edge AB crosses the edge CD.  We might remove that crossing by deleting the segments AB and CD from the drawing and replacing them with the edges AC and BD.
    1. Show that if AB and CD did cross, then AC and BD will definitely not cross
    2. Show that the resulting figure may be disconnected
    3. Show that if replacing AB and CD with AC and BD disconnects the figure, then replacing them instead with AD and BC will definitely not disconnect the figure, and that these two new edges will also not cross
    4. Show that in either case, the resulting polygon will have shorter total edge length
    5. Show by example that while this operation will eliminate the crossing of AB and CD, it may actually increase the total number of crossings in the figure
    6. Prove that the following algorithm will always result in a simple polygon:
      1. Let p1, p2, ..., pN be N points in the plane, no 3 on a line
      2. Draw the (not-necessarily simple) polygon p1 - p2 - ... - pN - p1
      3. find a pair of crossing edges (AB, CD), remove them and replace them with the pair (AC, BD) or (AD, BC), whichever keeps the polygon connected
      4. iterate step 3 until all crossings have been removed

  2. This question concerns how many simple polygons may be drawn through N points in the plane, N >= 3, with no 3 points on a line
    1. Prove that for 4 points, there may be more than one possible simple polygon
    2. Prove that for all N >= 3, there is some set of N points in the plane that has only one possible simple polygon with those points as vertices
    3. Let s(N) denote the maximum, over all configurations of N points, of the number of simple polygons that can be drawn through N given points in the plane.  For example, s(4) = 3 which can be proven as follows:  Consider the convex hull of those 4 points.  If it is a quadrilateral, then the only simple polygon through those points is the hull itself.  If the convex hull is a triangle, then consider the point inside the hull.  It must have two segments connecting it to other points in the set, and those points must be on the hull.  There are 3 ways to select those two points, and that uniquely determines the simple polygon.  Since no other hull is possible, we have s(4) = max(1, 3) = 3.  Find s(5).
    4. Construct an infinite family of examples to show that s(N) grows exponentially in N.  Note that a typical way to show that some function f grows exponentially is to show that f(N + a) = b·f(N), for some a > 0 and b > 1.


Program

The following Java program ought to compile (at least under a 4.2 compiler) without any trouble, and run:
     javac Simple.java
     java Simple
Your task is to rewrite the createSimplePolygon() function so that the "simple" tab draws a simple polygon through those points.

// Sample program
// Draws a bunch of points
// Then draws a random polygon through them.
//
// Your job is to make that polygon simple, by
// permuting the elements of the array C[], in
// the createSimplePolygon() function.
//
// Original by:  Robert Hochberg
// February 19, 2007
//
// Modified by:
//

import java.io.*;
import java.awt.*;
import java.awt.geom.*;
import java.awt.image.*;
import javax.swing.*;

public class Simple{
    static int POINTWID = 4;    // size of points
   
    // the x and y arrays hold the coordinates
    // the B array is the order of the points in the polygon
    // You want to fill the C array with the simple polygon
    static double x[] = new double[200];
    static double y[] = new double[200];
    static int B[] = new int[200]; // the permutation matrix
    static int C[] = new int[200]; // the one that becomes simple
    static SimpleFrame myFrame;
    static int numPoints = 3;
   
    public static void main(String args[]) {
    makePolygons();
   
    // Create the frame to draw on
    myFrame = new SimpleFrame();
    myFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    myFrame.setSize(600, 600);
    myFrame.setVisible(true);
    }   
   
    public static void makePolygons(){
    // Build an array of random points in the unit square
    for(int i = 0; i < numPoints; i++){
        x[i] = Math.random();
        y[i] = Math.random();// Sample program
        B[i] = i;        // default permutation
    }
   
    // Create the simple polygon
    createSimplePolygon();
    }
   
    /*
     * This is the only function you need to mess with
     */
    public static void createSimplePolygon(){
    // Initialize the C[] array with the identity permutation
    for(int i = 0; i < numPoints; i++)
        C[i] = i;

    // Bubble sort the points from left to right
    for(int i = 0; i < numPoints; i++)
        for(int j = 0; j < numPoints - 1; j++)
        if(x[C[j]] > x[C[j+1]]){
            int temp = C[j];
            C[j] = C[j+1];
            C[j+1] = temp;
        }
    }

    public static class SimpleFrame extends JFrame{
    public static JSlider numPointsSlider;

    public SimpleFrame()
    {
        super("Create you own Simple Polygon");
        Container content = getContentPane();
        content.setLayout(new java.awt.BorderLayout());
        JTabbedPane tabbedPane = new JTabbedPane();
        tabbedPane.setPreferredSize (new java.awt.Dimension(300, 400));
        tabbedPane.addTab("Scrambled", new ScrambledPanel());
        tabbedPane.addTab("Simple", new SimplePanel());
        content.add(tabbedPane, java.awt.BorderLayout.CENTER);

        // Slider for the number of points
        numPointsSlider = new JSlider (javax.swing.SwingConstants.HORIZONTAL,
                       3, 100, 11);
        numPointsSlider.addChangeListener (new javax.swing.event.ChangeListener () {
            public void stateChanged (javax.swing.event.ChangeEvent evt) {
            numPointsSliderStateChanged (evt);
            }
        }
                       );
        content.add(numPointsSlider, java.awt.BorderLayout.SOUTH);
    }
   
    private void numPointsSliderStateChanged (javax.swing.event.ChangeEvent evt) {
        numPoints = numPointsSlider.getValue();
        makePolygons();
        repaint();
    }
    }

    public static class ScrambledPanel extends JPanel{           
    public void paintComponent(Graphics g){
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;
           
        // First set the scaling to fit the window
        Dimension size = getSize();
        int Xwid = (int) (0.95 * size.width);
        int Ywid = (int) (0.95 * size.height);
           
        // First draw the segments
        g2.setColor(Color.red);
        for(int i = 0; i < numPoints; i++)
        g2.drawLine((int) (Xwid * x[B[i]]),
                (int) (Ywid * y[B[i]]),
                (int) (Xwid * x[B[(i+1) % numPoints]]),
                (int)(Ywid * y[B[(i+1) % numPoints]]));
           
        // Now draw the points
        for(int i = 0; i < numPoints; i++){
        g2.fillRect((int) (Xwid * x[i]) - POINTWID,
                (int) (Ywid * y[i]) - POINTWID,
                2*POINTWID + 1, 2*POINTWID + 1);
        }
    }
    }
   
    public static class SimplePanel extends JPanel{
    public void paintComponent(Graphics g){
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;
           
        // First set the scaling to fit the window
        Dimension size = getSize();
        int Xwid = (int) (0.95 * size.width);
        int Ywid = (int) (0.95 * size.height);
           
        // First draw the segments
        g2.setColor(Color.red);
        for(int i = 0; i < numPoints; i++)
        g2.drawLine((int) (Xwid * x[C[i]]),
                (int) (Ywid * y[C[i]]),
                (int) (Xwid * x[C[(i+1) % numPoints]]),
                (int)(Ywid * y[C[(i+1) % numPoints]]));
           
        // Now draw the points
        for(int i = 0; i < numPoints; i++){
        g2.fillRect((int) (Xwid * x[i]) - POINTWID,
                (int) (Ywid * y[i]) - POINTWID,
                2*POINTWID + 1, 2*POINTWID + 1);
        }
    }
  }
}