I need to select the points with in the regions that closest match the template, with the knowlede that the region may not contain any valid points.

A Voronoi diagram of your template will give you a set of "nearest-neighbour" regions. That is, each template point will have a Voronoi cell associated with it; every input point in that cell is closer to that cell's template point than to any other template point. (That would be so much easier to say in LaTeX math-mode.)

If your points are on a grid, you can build a bitmap from the Voronoi diagram, with a unique colour for each template point's Voronoi cell. Checking inputs is simply a matter of looking up their position in the bitmap (finding the colour, and thus which template point they're closest to), and calculating the distance to that point. Simple and O(n) once you have the Voronoi diagram.

In the continuous domain, things are probably a bit trickier. Find a good computational geometry text in your local university library; it should have plenty of stuff on this matter.