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.

  • $\begingroup$ How do you count lattice quadrilaterals with three collinear vertices? $\endgroup$ – Christian Blatter Feb 4 '14 at 19:45
  • $\begingroup$ 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. $\endgroup$ – Veritas Feb 4 '14 at 19:53
  • $\begingroup$ I have a O(m^2 n^2 k) algorithm for it, but I think it can be solved faster $\endgroup$ – Xeing Mar 26 '14 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.