Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been trying to make an algorithm to find the number of all possible simple quadrilaterals in a N*M lattice. I already have a brute force solution but since this is a Project Euler problem I believe it should be possible to solve much faster than I'm doing and so I'm taking a math approach instead. I haven't figured out much unfortunately. I tried to go about this using binomial coefficients and failed. Now I'm trying to use Pick's theorem which pretty much ensures we are dealing with simple polygons but I am not sure how to handle overlapping quads. The reason I'm posting therefore is to see if there is any other math approach I can take. I don't want any solutions just clues on the math part since I am not that educated on these math subjects.

Edit: I took a completely different approach so this has no need for me anymore. I am leaving it open for others.

share|cite|improve this question
    
How do you count lattice quadrilaterals with three collinear vertices? – Christian Blatter Feb 4 '14 at 19:45
    
In the old code using slopes. The very inefficient part of my previous code was checking which points can form 1 or 3 quads. I am sure there is a very elegant solution I'm not seeing. – Veritas Feb 4 '14 at 19:53
    
I have a O(m^2 n^2 k) algorithm for it, but I think it can be solved faster – Xeing Mar 26 '14 at 9:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.