"Is it possible to construct a triangulation by choosing the points in the space as we go along?": The answer is Yes. This is known as the incremental algorithm.
First, the Delaunay triangulation of $n$ points in $d$ dimensions can be extracted from the convex hull of a suitable set of $n$ points in dimension $d+1$. See the earlier MO question, "$n$-dimensional Voronoi diagram" and the references cited there.
Second, there are many incremental algorithms for computing the convex hull. One source is Chapter 22 of The Handbook of Discrete and Computational Geometry. The time complexities are roughly $O(n^{\lfloor d/2 \rfloor})$.
