For problem solving..

Question

This may be a bit OT...

Here's the problem: "N different points with integer coordinates are given in a plane. You are to write a program that finds the maximum number of collinear points (they all belong to the same line)."

Now my question: You don't have to solve this for me, instead I want to know where I can find some materials for learning how to solve problems like this. This is probably geometry related and I'm not really deep into geometry so I'd like to read up some advices, which books are good, where I can find any tutorials for solving such problems etc. etc.

Answer 1

The way to solve most problems that you can't see how to solve is to split into simpler parts that you can solve:

An O(n^3) algorithm is to iterate over every pair of points (P1, P2) and test for each other point whether or not it lies on the line P1 -> P2. For each pair you remember the count of the number of points that was on the line. You can find then find the maximum value of this count.

To test if three points A, B, C are collinear, you need to test if the vector (B - A) is a multiple of (C - A).

I won't give the code though. You should learn how to use vectors to represent lines, how to iterate over a set and produce all the pairs, etc. Most problems can be broken down into a combination of simpler techniques in this way. This won't always give you the optimum solution, but it may be good enough.

Answer 2

You need books on algorithms and basic thought patterns. Go to codechef, or projecteuler, or any other programming problem websites like that, they're RIPE with algorithms and hints on research to do. One way to solve the problem is the way you would do it by hand: take each two points, get the equation for that line, then check to see if any other points fit on it or not. If you only have one point on the plane, of course, the answer is 1.

Answer 3

where I can find some materials for learning how to solve problems like this

Unfortunately, solving algorithm problems, like most math problems, is a matter of reaching into your toolbox and using what you know. Very similiar problems may be solved in completely different ways, and there is no rule of thumb for knowing if a problem can be solved one way or the other, or even at all.

The best way to start, then, would be to build up your toolbox:

• Algorithms (free book)
• Intro to Algorithms (popular book)
• Project Euler (problem solving site)
• Forum dedicated to algorithms

Answer 4

These are some of computational geometry resources I found useful:

Books: Computational Geometry in C by Joseph O'Rourke Computational Geometry Algorithms and Applications (2nd edition) by de Berg et. al. Introduction to Algorithms by Cormen et. al. (Chapter 33)

tutorials: Geometry: Part I Basic Concepts (also check out the other parts in the series)

The books can be a little heavy for a beginner. I would suggest reading online tutorials first. You probably already know this, you can practice what you learn at sites such as TopCoder, SPOJ, Project Euler and UVa.

Answer 5

A simple solution is this that runs in O(N^2logN) is:

For each point get the angle of all other points and sort the points by this angle. Count the maximum number of points with the same angle. Then take the maximum number of all points. This will work since any collinear set of points has a start and ending point.

Now this solution has one short coming: It doesn't work with floating point points.

Implementing this will learn you how to handle angles in both a way that is accurate and doesn't end up possibly causing division by zero (vertical lines' gradient is undefined for instance)

Just one bit of advice for solving problems like this: Be aware of all possible edge cases that might cause your code to break, this is what generally makes these types of questions hard and if you're not careful you might get code that works most of the time but not always.

Answer 6

How about using a point-line duality to replace this problem by a problem of finding the maximum number of lines that intersect in the same point? I.e. each point p=(a,b) becomes a line ax + b, and you want to find how many of these lines intersect in the same point.

You can solve this new problem with a topological sweep in quadratic time. Albeit, you have to be careful since you are explicitly looking for a degeneracy.

Answer 7

The single most effective way I know of solving problems is to have heard them before and know the answer already. In fact I don't know of another method remotely as good. This definitely applies to this problem for me, because when I first heard of http://en.wikipedia.org/wiki/Hough_transform it looked like something completely out of the blue. If I had to provide a way of getting there, I would either propose the idea of canonicalisation (simple example - converting all strings to upper case to do comparisons without case) or consider who might have already solved this problem - in this case particle physicists.

I see the Wikipedia entry references an article about how the Hough transform was invented, but the IEEE will probably want unreasonable amounts of money to let you see it.