Mapping random points on a sphere onto a uniform grid

Question

Say I had an arbitrary sphere that is covered in a uniform triangle mesh of N elements with each element having a unique sequential index.

If given the coordinates of a random point on the surface of the sphere is it possible to map the point to the mesh element it is contained in without using the vertices data of the mesh?

i.e find the index of the mesh element a random point lies on,

For example can the fact that the mesh is uniform be exploited in mapping the point to a particular element.

Either analytical or approximate methods would be of interest.

Further information

An example of a uniform triangle mesh on a sphere :

Answer 1

Without any claims to optimality, a feasible solution would be

1. Divide the latitude range $[-90°, 90°]$ into equal steps, forming a set of equidistant rings around your sphere.
2. For every such ring, divide the longitude range $[-180°, 180°)$ into steps such that each quadrilateral formed will have almost equal side lengths.

Using these, you could compute the coordinates of the quadrilateral for a given point from the latitude and longitude of that point, simply by multiplying them with a constant and rounding afterwards.

This idea was inspired by Figure 3 of the paper Raskolnikov mentioned in a comment above.