Can we actually find any fixed points with Brouwer's theorem? Background
At the risk of greatly oversimplifying matters, let me state a heuristic from Granas and Dugundji's beautiful book: fixed point theorems fall into two broad categories. The first class is usually functional analytic and imposes strong conditions on the map $f:X \to X$ whereas the second class is usually algebraic topological and imposes strong conditions on the space $X$ itself.
A typical example of the first class of theorems is the fixed point theorem of Banach. While the spaces it applies to are fairly general (complete metric spaces), the function must have a Lipschitz constant strictly less than $1$. On the other hand, Brouwer's theorem falls into the second class. Any continuous map works, but the domain must be a compact and convex subset of Euclidean space (originally a disk). Of course, both these theorems have been vastly generalized from the versions that I am stating here.
Question
One fundamental advantage of the Banach theorem is that it actually provides a recipe for converging to the fixed point as part of the standard proof: just start at an initial point and iterate. The proofs of the Brouwer theorem that I have seen do no such thing. The best known proof (I think) is the one by contradiction: assuming the domain is a disk, if $f(x)$ and $x$ are always distinct then the ray from $f(x)$ through $x$ to the boundary of said disk provides a deformation-retraction from the disk to its boundary, aha!
Here is my question:

Is there any way to actually find a fixed point when using Brouwer's theorem?

A Possible Idea
One scheme that unfortunately fails is as follows. Consider the sequence of iterates $f^n(x)$ for $n \in \mathbb{N}$ and any initial $x$ in the domain. We have an infinite sequence in a compact set, and hence a convergent subsequence, so the limit point is a candidate. This won't work since a) we haven't used convexity at all, and b) one may just be converging to a periodic orbit of $f$. 
 A: There are other constructive proofs Here is an article with a method which , according to the authors,  does not require a simplicial decomposition,is similar to Newton's method, and has been applied up to dimension $60$. 
A: (This answer is in a similar direction to that of Johannes Hahn's and to Will Sawin's)
I think (I am not 100% sure) that one may get away without doing the triangulation and simplicial approximation (of the "usual" Sperner's Lemma proof) if you take the approach using van Maaren's version of Sperner's Lemma (there is an outline of the proof in Schechter's Handbook of Analysis and its Foundations with some typos). 
One first obtains the van Maaren's version of Sperner's Lemma, which is purely combinatorial/order theoretical and is a constructive statement on finite sets (the proof just gives the algorithm). 
Using that one gets an approximate fixed point statement (roughly speaking for every $\epsilon$ you find a point that is $\epsilon$ away from being a fixed point). To get the approximate fixed point at size $1/k, k\in\mathbb{N}$ you only need to consider the finite subset formed by the lattice of spacing $1/(3kn)$ where $n$ is the dimension. In this step the convexity comes into play (but not continuity; compactness only enters via Heine-Borel as boundedness). 
Note that this does not require being able to approximate the function $f$: it just requires being able to evaluate $f(x)$ for given $x$ to arbitrary accuracy (in particular you need to know whether the $i$-th coordinate of $f(x)$ is less than or equal to the $i$-th coordinate of $x$). 
Then you take limit as $k\to \infty$ (and here continuity and compactness are used, by convexity is no longer relevant) (the practicality of this last step, of course, is questionable; and as Noam Elkies and Michael Greinecker alluded to, this method gives no rate of convergence, so cutting off the computation at a finite $k$ doesn't guarantee that you are near a bona fide fixed point at all). 
A: Here's a paper worth checking out: http://arxiv.org/abs/1206.4809. It essentially shows that finding a fixed point of a continuous $f:[0,1]^{n} \to [0,1]^{n}$ is as hard as finding a point in a nonempty connected closed subset of $[0,1]^{n}$.
They also mention (after Theorem 1.1) that the Brouwer fixed point theorem is non-constructive.
A: There is a constructive version of Brouwer's theorem via Sperner's theorem. This gives an actual way to compute fixed points. (Not a very efficient one, granted, but an algorithm nonetheless)
A: The paper "Exponential lower bounds for finding Brouwer fixed points"
Addendum by original poster: It was non-trivial to find a copy of this great paper of Hirsch, Papadimitriou and Vavasis. It does answer my general question quite clearly: finding Brouwer fixed points is exponentially hard in the worst case no matter what algorithm you use. Here is a link to this paper for all those who are interested and don't want to run into many, many pay-walls. I will take it down in a few days. -VN
A: This is perhaps silly, but the obvious algorithm for $\mathbb R^1$ is to compute $f(1/2)$. If it's larger than $1/2$, compute $f(3/4)$. If it's smaller, compute $f(1/4)$. Keep going dyadically and you will compute the binary digits of a fixed point to an arbitrary level of accuracy. But it's very unclear how to generalize this.
If all we can do is sample the function at finitely many points, it should be impossible to guess the location of a fixed point with any degree of accuracy. To see this, take a function with a single fixed point, like $f(x)=.99x$. Take a long but very thin tube containing that point and another point, and change the function on the tube so that the other point is now the fixed point.
Since the measure of the tube can be made arbitrarily small, and the tube can be chosen to avoid any finite set, any strategy for sampling finitely many points will, with high probability, be unable to distinguish the function from $.99x$ and so will be unable to guess the location of the fixed point.
Thus, you need some way to show the function is not malevolent, like some understanding of the $\epsilon$s and $\delta$s in the function's uniform continuity, or maybe a probabilistic model of a random function.
