"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][1]" 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_][2].
The time complexities are roughly $O(n^{\lfloor d/2 \rfloor})$.


  [1]: https://mathoverflow.net/questions/49516/
  [2]: http://www.crcpress.com/ecommerce_product/product_detail.jsf?catno=C3014&isbn=0000000000000&parent_id=&pc=