I really don't understand the context of what you want to achieve and what are the limitations. For example, is there a strict requirement that divided regions be equal in size?
Often, solving a performance problem is not a fast algorithm, but a different approach, usually one or more of the following:
Pre-compute values ββor calculate as many offline as possible. Say, using a different server API that can execute a unit offline and cache the results for multiple clients. You can use the post-calculated result as a bitmap, where each color is indexed into a table of values ββthat you want to display. Finding the value will be a simple matter of indexing the pixel at the touch position.
Simplify or make the solution closer. Would grid division be enough? With 500 x 6 = 3,000 units, you only have about 51 square points for each region, which is about 7x7 points. With this size, the user will not notice whether the region is absolutely accurate. You may need to eventually aggregate neighboring regions due to sensory resolution.
Progressive refinement. You often do not need to compute the entire algorithm forward. Very often, algorithms work in discrete (often symmetric) units, which means that you often reuse information from the previous steps. You can only calculate the first step forward, and then use the background stream to gradually fill in the rest of the part. You can also postpone the final settlement until a touch appears. A delay of up to a second is still portable at this point, or in the worst case, you can display the animation during the calculation.
You can use a hybrid approach and possibly calculate one or two levels using Delaunay triangulation, and then use a simple, quick triangular division for two more levels.
Depending on the required accuracy, and if restrained samples are not required, the final levels can be approximated using the weighted average value between the points of the triangle, that is, if the touch is halfway between two points, select the average value between them.