Homework 6, Due Friday, 3/6 by 5:00 pm via ICON

Introduction.
The input is a set P of points in the plane (say, in a window W) and a positive integer k. Your task is write a program that determines if it is possible to place a k × k square in W so that it is empty (i.e., does not contain any point in P).

For example, here is a 500 × 500 window containing 3000 points. If k were 20, your task would be to see if you can locate a 20 × 20 square somewhere in this window, so that it is empty. Do you see the 20 × 20 empty square that was found by a program I wrote?

graph 1

Input and Output.
The input will come from a text file containing the set P of points. You can assume that your text file looks like this: 

		10 52
		109 399
		12 70
		15 402
		150 100
In this example, the text file contains 5 points, one point specified in each line, with the x-coordinate specified first, followed by some blanks and then the y-coordinate. This file may contain arbitrarily many points. However, you may assume that all coordinates are integers in the range 1 through 500. As a result you can also assume that window W in which you are expected to search is a 500 × 500 window. After your program has read this file, it should prompt the user for a value of k (you can use the JES function requestInteger for this). Now your program is ready to look for an empty k × k square in the window W. After your program has completed this search, it should produce a 500 × 500 window with all the points in P. If your program was able to find an an empty k × k square, it should display the square as well in the window; otherwise it should display a text message -- something like "Empty Square Not Found."

Searching for an empty square.
At first glance, it might seem as though you might have to try out infinitely many possible placements of the k × k square and check each placement for emptiness. However, it turns out that we can turn this into "finite" search pretty easily. Imagine for the moment that it is possible to place an empty k × k square S in the window. Now try to move S as far to the left as possible (without violating its emptiness). Similarly, try to move S as far up as possible (without violating its emptiness). Now S is guaranteed to either be flush against the left side of the window or have a point p in P flush to its left side. Similarly, S is also guaranteed to either be flush against the top side of the window or have a point q in P flush to its top side. This means that we only have to examine k × k squares that are:

  1. flush against the left side and the top side of the window (there is only one such square),
  2. flush against the left side of the window and with a point in P touching the top side,
  3. flush against the top side of the window and with a point in P touching its left side, and
  4. flush against a point p in P on its left and a points q in P on its top.
Item (4) takes the most work, but it is easy to describe the algorithm you will need to use for this case, at a high level (given in pseudocode below): 
	for each pair of points p and q in P do
		if there is a k × k square S that has p flush to its left and q flush to its topthen
			check if S is empty
For now, to check if S is empty or not, you can simply use linear search.

How to get started.
There are three distinct parts to your program: (i) reading input, (ii) doing the search, and (iii) producing the output (i.e., drawing a window, points, and square). The search is the most important part of your program and will be worth a large fraction of the points and so you should first focus on making as much progress on your search as possible, leaving the input and output for later. Specifically, if you don't want to deal with file input for now, you could just generate a list of points at random. Here is a simple function to do this, in case you want to use this approach. 

# Generates and returns a list of n points, each having integer 
# coordinates in the range 1 through m
def generatePoints(n, m):
  l = []
  for i in range(0, n):
    l = l + [[random.randint(1, m), random.randint(1, m)]]
  return l
As far as output is concerned, in order to get things going, you could start off by having your program just use printNow() to print a message such us "Found an empty square with northwest corner 10 15." You can think about making a window, drawing points and squares, etc. later.

What should you do over the weekend?
 In order to help you get started on this homework over the weekend, let me suggest a very specific task. Write a python function: 

	def isEmpty(ptList, nw, se):
that returns true if the rectangle whose northwest corner is given by nw and southeast corner is given by se, does not contain any points in ptList. The function should return false otherwise. You may assume that nw and se are length-2 lists of integers (for e.g., nw = [8, 20], se = [25, 30]) and ptList is a list of length-2 lists (e.g., ptList = [[20, 11], [4, 5], [7, 22], [11, 34]]).

What to submit.
Submit a python program to solve the above problem in a file called hw6.py. This file should contain a function main() that should get the program going. Your program should be well commented and easily readable. In addition, submit a README file (see instructions on the course page).