Your model of what you do mentally is incorrect. In fact, you operate in two steps:

1. Eliminate all points that are too far, in $O(1)$ time.
2. Measure the $m$ points that are about as close, in $\Theta(m)$ time.

If you've played games like pétanque (bowls) or curling, this should be familiar — you don't need to examine the objects that are very far from the target, but you may need to measure the closest contenders.

To illustrate this point, which green dot is closest to the red dot? (Only by a little over 1 pixel, but there is one that's closest.) To make things easier, the dots have even been color-coded by distance.

This picture contains $m=10$ points which are nearly on a circle, and $n \gg 10$ green points in total. Step 1 lets you eliminate all but about $m$ points, but step 2 requires checking each of the $m$ points. There is no a priori bound for $m$.

A physical observation lets you shrink the problem size from the whole set of $n$ points to a restricted candidate set of $m$ points. This step is not a computation step as commonly understood, because it is based on a continuous process. Continuous processes are not subject to the usual intuitions about computational complexity and in particular to asymptotic analysis.

Now, you may ask, why can't a continuous process completely solve the problem? How does it come to these $m$ points, why can't we refine the process to get $m=1$?

The answer is that I cheated a bit: I presented a set of points which is generated to consists of $m$ almost-closest points and $n-m$ points which are further. In general, determining which points lie within a precise boundary requires a precise observation which has to be performed point by point. A coarse process of elimination lets you exclude many obvious non-candidates, but merely deciding which candidates are left requires enumerating them.

You can model this system in a discrete, computational world. Assume that the points are represented in a data structure that sorts them into cells on a grid, i.e. the point $(x,y)$ is stored in a list for the cell $(\lfloor x \rfloor, \lfloor y \rfloor)$. If you're looking for the points that are closest to $(x_0, y_0)$ and the cell that contains this point contains at most one other point, then it is sufficient to check the containing cell and the 8 neighboring cells. The total number of points in these 9 cells is $m$. This model respects some key properties of the human model:

• $m$ is potentially unbounded — a degenerate worse case of e.g. points lying almost on a circle is always possible.
• The practical efficiency depends on having selected a scale that matches the data (e.g. you'll save nothing if your dots are on a piece of paper and your cells are 1 km wide).

For the same reason when you look at a triangle and know it is a triangle you are forgetting the many millions of calculations you do without noticing it.

Neural networks

In effect you are a neural network that has been trained and loaded with masses upon masses of data.

Take the infant shape sorting game as an example:

When a child first interacts with this it is likely they will attempt to insert shapes into the wrong holes, this is because they have not yet trained their brain or encountered enough data to build networks. They can't make assumptions about edges, size, .etc to determine which shape fits the hole.

This seems obvious to you (I hope) because you have built these connections, you may even think it is intuitive and not have to break it down, for example you just know the triangle fits the triangle and don't need to approximate the size, count the edges, .etc. This is not true, you have done all that in your subconscious, the only conscious thought you had was that it is a triangle. Many millions of computations happened from taking a visual representation, understanding what it was representing, understanding what the individual elements are and then estimating their distances, the fact that you had a large database of information to poll against made this simpler.

Your brain isn't binary

The data your brain works on isn't binary (As far as we know), isn't true or false, it holds many states that we use to interpret the data, we also get things wrong often, even when we follow the correct process, this is because the data changes often. I would hazard a guess that our brains function a lot more like a quantum computer would where the bits are in an approximate state until read. That is, if our brain works like a computer at all, it really is not known.

Hence an algorithm for working with binary data will not work the same. You can't compare the two. In your head you are using concepts to perform, rich data types that hold far more information, you have the ability to craft links where they are not explicitly defined; upon seeing a triangle you may think of Pink Floyd's Dark side of the moon cover.

Back to the scatter graph, there is no reason you couldn't do this on a computer using a bitmap and measuring the distance from a point in increasing radii until you encountered another point. It is possibly the closest you could get to a human's approximation. It is likely to be much slower because of the data limitation and because our brains don't necessarily care about computation complexity and take a complex route to do things.

It wouldn't be O(1), or even O(n) if n is the number of points, instead its complexity now depends on the maximum linear distance from the point selected to a bound of the image.

tl;dr

Your brain is not a binary computer.

My interpretation of the question:

I do not believe this question is to be taken simplistically as a a computational geometry complexity issue. It should be better understood as saying: we perceive an ability to find the answer in constant time, when we can. What explains this perception, and up to this explanation and to human limitations, can a computer do as well.

Thus the question should probably be seen first as a question for a psychologist. The issue is probably related to your perception of time and effort. Can you brain really perceive a difference between $O(1)$ time and $O(log( n))$ time? Specific counter examples do not really matter, as in issues of perception we tend to think instinctively of average cost (complexity being probably to precise a concept psychologically). More accurately, we are more interested in the common case, than in special cases when we feel we cannot readily answer the question.

This may be reinforced by the Weber-Fechner laws, that states that our perception is to be measured on a logarithmic scale of the actual physical measure. In other words, we perceive relative variations rather than absolute variations. This is for example why sound intensity is measured in decibels.

If you apply this to the perception of the time we use to find the closest point, this is no longer $O(log (n))$ but $O_\psi(log (log (n)))$, where $O_\psi$ is my just invented Landau notation for "psychological complexity".

Actually I am cheating, because the psychological perception of the scatterplot graph size also obeys the logarithmic law, which should compensate in this simple complexity relation. Still, it means that a scatterplot will alsways seem much simpler to us than it really is, especially for very large ones. But whatever the size we perceive, if we have a built-in logarithmic algorithm to find a closest point (such as neuronal quadtrees), then the perceived processing time is to be mesured by $O_\psi(log (log (n)))$ which for all practical purposes is probably perceptually undistinguishable from a constant, and ther is necessarily some constant time added to it to start the recognition process and acknowledge the result.

Taking into account the physiological limitations

The above conclusion is further sustained when considering the image acquisition steps.

The OP was careful to separate the construction of a proper data structure, "such as a quadtree", which is amortized on several queries.

This does not work for most people who do not memorize the image. I think the image is scanned for each query, but that does not imply scanning all points: not the first time, and not for later queries.

The eyes scans a raster image, in constant time $T_{scan}$, idenpendently of the size of the scene taken in, and with a fixed resolution defined by the retina structure (see below). Thus it gets a constant amount of information, possibly not distinguishing all points. It can then focus on the relevant part of the image, to distinguish relevant points in another time $T_{scan}$, plus possibly the time to change the orientation and focus of the eye. Theoretically, this operation could have to be repeated, leading to logarithmic focussing, but I believe that in perceptual practice, there is at most one additional step for focussing vision.

Scanning probably results in a structure in the brain that can be analyzed to find the answer. It may still contain a very large number of points. Though I do not know how the brain proceeds, It is not unreasonable to think that it is some kind of focussing process that takes at worst logarithmic time, possibly even less. This process is applied to the perceived image, that has a bounded size. This implies of course a bounded number of points, though it can be quite large. Thus there is a fixed upperbound $m$ to the information to be processed. Assuming logarithmic processing, and reusing the above analysis, the perceived processing time is $O_\psi(log (log (m)))$.

The resolution of the human eye is fixed by the number of rods, which is about 125 millions. That is about $2^{27}$. Using base 2 for the logs, that gives for the processing an upperbound of about $log_2(27)$, i.e. about 5 steps of whatever cost there is for a step. Using instead the estimated value of the eye resolution which is on the order of 500 megapixels does not change the final result.

Without knowing the actual units to be used, this simply shows that the variation for processing is at worst on the same order as other constant time operations. Hence, it is quite natural that the perceived time for finding the closest point feels constant . . . whether we determine the closest point or only a set of the closer points.

About counter-examples and a possible solution

It is of course easy to build counter-examples that make eyes determination of the closest point very difficult among a small collection of the closer points. This is why the OP is actually asking for an algorithm that eliminate quickly most of the points, except for the closest ones. This issue of the possible difficulty of chosing among several close points is adressed in many answers, with the paradigmatic example of closest points being almost on a circle around the reference point. Typically the Weber-Fechner laws precludes being able to distinguish small distance variations over long enough distances. This effect may actually be increased by the presence of other points which, though eliminated, may distort the perception of distances. So trying to identify the closest point will be a harder task, and may well require specific examination steps, such as using instruments, that will completely destroy the feeling of constant time. But it seems clearly outside the range of experiments considered by the OP, hence not very relevant.

The question to answer, which is the question actually asked by the OP, is whether there is a way to eliminate most of the points, except possibly for the remaining few which seem to have very similar distances to the reference point.

Following our analysis of what may be hidden behind a perceived constant time, a computer solution that does it in $O(log(n))$ time could be considered satisfactory. On the other hand, relying on amortized cost should not really be acceptable, since the brain does not do it that way, afaik.

Rejecting amortized cost does not allow for a computer solution, since all points have to be looked at. This underscores a major difference in the computing power of the brain and of human perception: it can use analog computation with properties that are quite different from digital computation. This is typically the case when billions of points are not distinguishable by the eye, which does not have the resolution to see anything but a big cloud with various shades of dark. But the eye can then focus on relevant smaller part, and see a bounded number of points, containing the relevant ones. It does not have to know of all points individually. For a computer to do the same, you would have to give it a similar sensor, rather than the precise numerical coordinates of each point. It is a very different problem.

"Mere visual inspection" is in some respects a lot more powerful than digital computation. And it is due also to the physics of sensors, not just to a possibly greater computing power of the brain.

Nobody has mentioned that this problem can be solved very quickly on a computer with a spatial index. This is the equivalent of plotting out the points in an image for your eyes to scan quickly and eliminate most of the points.

There is a very good indexing algorithm used by Google and others to find the nearest point(s) called a Geohash. http://en.wikipedia.org/wiki/Geohash.

I think that this will even up the contest in favour of the computer. I was not impressed with some of the answers that used linear thinking.

other answers are good but how about a zen counter question that stretches the basic reasoning/premise of the original question to extremes to show some faultiness [but is also the paradox at the core of AI research]:

if I can think with human intelligence, why cant I create a computer that thinks as well as a human?

there are multiple ways to answer your question, but basically, our thought processes and brain perceptual capabilities are not necessarily accessible to introspection, and the introspection we do apply to them can be misleading. for example we can recognize objects but we have no way to perceive/explain the quasi-algorithmic process that goes on to allow this. also there are many psychology experiments that show there are subtle distortions in our perceptions of reality and in particular time perception, see eg time perception.

it is generally thought/conjectured by scientists that the human brain does in fact employ algorithms but they function differently than computerized ones, and also there is a very large amount of parallel processing going on in the brain via neural networks that cannot be compared sensibly to sequential computer algorithms. in mammals, a significant percentage of the entire brain volume is dedicated to visual processing.

in other words human brains are in many ways highly optimized visual computers, and they do in fact in many ways have a capability that exceeds the worlds greatest supercomputers currently, such as in object recognition etcetera, and that is due to deficiencies (in comparison) in human-constructed software/hardware in comparison to biology that has been highly tuned/evolved/optimized over millions of years.

Generally speaking you are solving two different problems and if you compete in the same competition, complexity will be O(1) for both of you. Why? Let's make situation a bit simpler - assume that you have a line with one red point and n green points. Your task is to find green point which is closest to red point. Everything is on the graph. Now what you do and what you program is doing is basically the same - just "walk away"(in both directions) from red point and check whether the pixel you are looking at is white/black(background) or green. Now the complexity is O(1).

What's interesting is that some data presentation methods gives answers to some questions immediately(O(1)). Basic example is extremely simple - just count white pixels on black image(each pixel value is 0 = black or 1 = white). What you need to do is just add all pixels values - complexity is the same for 1 white pixel and for 1000, but it depends on image size - O(m), m=image.width*image.height. Is it possible to do it faster? Of course, all we need to do is use different method of storing images which is integral image: Now calculating the result is O(1) (if you have integral image already calculated). Another way is just store all white pixels in array/vector/list/... and just count it size - O(1).