# Minimizing Grid Mapping time of Protein Surface

This is an interesting problem - I was wondering if anyone has a creative solution.

So I have a vector of vertices representing atoms in a protein, as well as 6 variables containing the absolute minimum/maximum bound of the set at each direction.

I need to build a grid that surrounds the protein/vertices in a homogeneous layer.

Right now I just loop through every square of the grid bound by the minimum-maximum values and then loop through every vertex to calculate the minimum distance between my point and every atom in the protein, and see if that point is at an acceptable distance. This process is quite expensive.

Do you guys have any creative answers as to how minimize the time?

Thanks!

P.S. the list of atoms in the protein are ordered more according the the amino acid sequence, which means it has almost no relation to the location of the atom in space

• IIUC you are looking for what is described in wikipedia under the name Cell lists – marcin Jun 29 '17 at 16:30
• The question is clear to me apart from the sentence "build a grid that surrounds...". Usually you define a grid with a spacing of your choice and then only assign numbers to the nodes in the grid. Maybe you could edit the question and elaborate. – marcin Jun 29 '17 at 16:42
• I think OP is trying to find the surface of the protein (?) I agree, the problem needs to be clarified – galicae Jun 30 '17 at 9:20
• Your friend is the sort function/method, which is O(n log n), while a nested loop is O(n^2). – Matteo Ferla Nov 5 '19 at 14:36