Take the 2-minute tour ×
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.

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|improve this question
    
How do you count lattice quadrilaterals with three collinear vertices? –  Christian Blatter Feb 4 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 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 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.