We have selected the latter option because it is the fastest and the implementation is fairly easy. The algorithm we use is to

- 1.
- Iteratively select a group of two rays (in the 2-D case) or three rays (in the 3-D case) according to the take-off angle(s) so that the entire data space is eventually covered.
- 2.
- Select two doublets of points (in the 2-D case) or triplets of points (in the 3-D case) on the considered rays. They act like a base with two (in 2-D) or three (in 3-D) ``candidate' points.
- 3.
- Analyze all the candidates to see which best fits the Delaunay criterion. This procedure translates into performing an in-circle test (in 2-D) or an in-sphere test (in 3-D) O'Rourke (1993).
- 4.
- Advance the base with the point selected at the proceeding item, and proceed to the next step by selecting a new group of candidate points. Of course, only one will be different from the proceeding group of candidates.

Figure 2

A difficult situation appears when the candidate points are not on the same side of the advancing base. In such cases, it is no longer possible to apply only the Delaunay criterion. Other rules are needed to get the correct new base. Our choice is to advance the points on the ray that restore fastest all the candidate points on the same side of the base. We do so by saving the ray of the last advance and performing the new advance on one of the other rays.

10/9/1997