COS 226 Programming Assignment Checklist: Pattern Recognition

Frequently Asked Questions

Can the same point appear more than once as input to Brute or Fast? You may assume the input to Brute and Fast are N distinct points. Nevertheless, the methods implemented as part of the Point data type must correctly handle the case when the points are not distinct: for the areCollinear() methods, this requirement is explicitly made in the assignment; for the comparison methods, this requirement is implicit in the contract for Comparable and Comparator.

The reference solution outputs a line segment in the order p→q→r→s but my solution outputs in the reverse order s→r→q→p. Is that ok? Yes, there are two valid ways to output a line segment.

The reference solution outputs the line segments in a different order than my solution. Is that ok? Yes, if there are k line segments, then there are k! different possible ways to output them.

Can I draw a line segment containing 4 (or more) points by drawing several subsegments? No, you should draw one (and only one) line segment for each set of collinear points discovered: You should draw the line segment p→q→r→s, with either p.drawTo(s) or s.drawTo(p).

How do I sort a subarray? Arrays.sort(a, lo, hi) sorts the subarray from a[lo] to a[hi-1] according to the natural order of a[]. You can use a Comparator as the fourth argument to sort according to an alternate order.

Where can I see examples of Comparable and Comparator? See the textbook, lecture slides, and go to precept. We assume this is new Java material for most of you, so don't hesitate to ask for clarifications on Piazza.

My program works correctly except on (some) vertical line segments. What could be going wrong? Are you dividing by zero? With integers, this produces a runtime exception. With floating-point numbers, 1.0/0.0 is positive infinity and -1.0/0.0 is negative infinity.

I'm having trouble avoiding subsegments Fast.java when there are 5 or more points on a line segment. Any advice? Not handling the 5-or-more case will lead to only a minor deduction, so don't kill yourself over it.

Why are most of the line segments in the input files horizontal and vertical? We generate most of the data sets at random. Since the points have integer coordinates in a small range, there are more opportunities to form horizontal and vertical lines.

I created a nested Comparator class within Point. Within the nested Comparator class, the keyword this refers to the Comparator object. How do I refer to the Point instance of the outer class? Use Point.this instead of this. Note that you can refer directly to instance variables and methods of the outer class; with proper design, you shouldn't need this awkward notation.

Why aren't I allowed to change the pen color or pen radius? It will mess with our grading script.

Testing

Testing Point.java. Have your main() create points that form a horizontal line, then a vertical line, and finally a line with a slope somewhere between the two. Make sure that if p→q→r is collinear, then so are r→q→p, p→r→q, and so forth.

Input. The directory collinear contains some sample input files. Thanks to Jesse Levinson '05 for the remarkable input file rs1423.txt.

Reference solutions. Some of the input files have associated .png files that contain the desired output. You can use these for checking your work.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

Getting started. Download the directory collinear to your system. It contains a number of sample input files and some helper programs.
The files Point.java and PointPlotter.java comprise a program that reads in a list of points and plots the results. To plot the points, type the following at the command line
```
% javac PointPlotter.java
% java PointPlotter < input56.txt
```
This opens a standard drawing window where you will see the points plotted.
Collinearity. To begin, implement the 3-argument areCollinear() method. Be sure to consider a variety of corner cases: points on a horizontal line, points on a vertical line, 2 or more points are equal, and so forth. Then, implement the 4-argument areCollinear() method. You may wish to call the 3-argument areCollinear() method. Thoroughly test it.
Brute force algorithm. Write code to iterate through all 4-tuples and check if the 4 points are collinear. To draw the line segment, you need to know the endpoints. One approach is only to print out a line segment if the 4 points are in ascending order (say, relative to the natural order), in which case, the endpoints are the first and last points.
Hint: don't waste time micro-optimizing the brute-force solution.
Fast algorithm.
- Implement the SLOPE_ORDER comparator in Point. The complicating issue is that the comparator needed to compare the slopes that two points q and r make with a third point p, which changes from sort to sort. To do this include a public and final (but not static) instance variable SLOPE_ORDER in Point of type Comparator<Point>. This Comparator has a compare() method so that compare(q, r) compares the slopes that q and r make with the invoking object p.
- Implement the sorting solution. Watch out for corner cases. Don't worry about 5 or more points on a line segment yet.

Enrichment

Can the problem be solved in quadratic time and linear space? Yes, but the only algorithm I know of is quite sophisticated. It involves converting the points to their dual line segments and topologically sweeping the arrangement of lines.

Can the decision version of the problem be solved in subquadratic time? The original version of the problem cannot be solved in subquadratic time because there might be a quadratic number of line segments to output. (See next question.) The decision version asks whether there exists a set of 4 collinear points. This version of the problem belongs to a group of problems that are known as 3SUM-hard. A famous unresolved conjecture is that such problems have no subquadratic algorithms. Thus, the sorting algorithm presented above is about the best we can hope for (unless the conjecture is wrong). Under a restricted decision tree model of computation, Erickson proved that the conjecture is true.

What's the maximum number of (maximal) collinear sets of points in a set of N points in the plane? It can grow quadratically as a function of N. Consider the N points of the form: (x, y) for x = 0, 1, 2, and 3 and y = 0, 1, 2, ..., N / 4.