## An empirical comparison of techniques for updating delaunay triangulations

Some applications of Delaunay Triangulation include: A Delaunay Triangulation connects the nearest neighbors in a neighborhood; hence it can be used to model the collision detection problem. The Delaunay Triangulation structure is efficient due to each point in the triangulation representing an object in the environment, and then it is checked against neighboring objects to preserving the Delaunay structure and the edges connection.

However, the movement of at least one point in a Delaunay Triangulation can produce changes in the structure, and, consequently, it is necessary to update the Delaunay triangulation in order to model dynamic phenomena. Triangulation The goal of a triangulation is to produce a mesh. Meshes are a common way to represent continuous surfaces. The input of a Triangulation is a set of points and the result is a set of triangles or linked edges without overlapping [Zim05].

Building a Triangulation has different problems, but the starting point and the dispersion should not be important. Greedy Triangulation [DDMW94] is used to triangulate simple polygons by linking together closest points; as a result, shortest edges are generated for the set of points.

A triangulation is created, but it may or may not be a Delaunay Triangulation. For the set of points P shown in figure 1a a Delaunay Triangulation is created in figure 1b. A convex hull for P is depicted in figure 1c. Whereas figure 1d depicts the circumcircles, figure 1e shows the centers for each circumcircles. Finally, the Voronoi Diagrams is represented in figure 1f.

Delaunay Triangulation Algorithms In figure 2a three new triangles are created when a new point p falls inside a triangle, whereas two new triangles are created if p falls into an edge see figure 2b. Two adjacent triangles are shown in figure 2c four new triangles are created as shown in figure 2d.

Because there are not any overlapping triangles in a Delaunay triangulation, new ones replace old ones. Incremental Algorithms Incremental Insertion: The algorithm has three parts: For the triangulation, the first point is inserted in the triangle t, and three new triangles are built t1, t2 and t3 , then t is replaced by the new triangles see figure 2a.

Inserting the second point, can be divided into two ways: If a unique triangle is found, two new triangles will replaced the old one see figure 2b. If two triangles are found, the pair of triangles will be deleted, and four new triangles will be built for each triangle, two new ones are constructed as depicted in figures 2c and 2d.

Finally, it is necessary to review the circumcircle condition for each new triangle, and repeat the way to insert the second point [Law77]. In the last part, the triangles that include the vertex of the first triangle is deleted. Sweepline Algorithms Plane Sweep Algorithm: A line sweeps the points, when a point is found by the line this is inserted in the triangulation.

It only works in two-dimensions. This implementation is based on the uniqueness property of a Delaunay Triangulation. In each step, one new edge or triangle Delaunay is added until completing all points in the set P. First, to find a Delaunay edge, then, create a new triangle Delaunay by searching a point p [HD06]. To find a point near to the center of the complete set of points, this point is labeled one.

A first edge is built with the closest point and labeled two, the next step is to create the first triangle, following the right-hand rule, it is labeled three and the next point is labeled four and so. An improved algorithm was constructed based on a higher subdivision of the grid [PLK05]. An arbitrary triangulation is constructed; it is optimized to generate a Delaunay Triangulation. This is a recursive way to calculate Delaunay. The area is subdivided into two parts, and the triangulation is computed recursively in each part.

Finally, both triangulations are merged together; however, merging is the most complex step [HD06]. The name is short for Delaunay Wall. It is a Divide and Conquer algorithm, which computes the simplices between the subdivisions before, in other words, the algorithm merges to calculate recursively the Delaunay Triangulation [CMS97]. A circumcircle is a unique circle passing through each vertex of the triangle in a Delaunay Triangulation DT P.

The circle contains no other point from the set of points P, see figures 3a and 3b. It was introduced by Sibson in [Sib78]. For each quadrilateral in Delaunay Triangulation DT P , two possible triangulations can be produced, the correct ones maximize the minimum of the six internal angles see figures 3c and 3d.

Delaunay Triangulation DT P , for a set of points P, is unique, except for a set of four co-circular points; it is called a degenerate case, for instance: A degenerate case happens when four or more points fall into a circumcircle in two dimensions or five or more points fall into a circumsphere in three dimensions.

For more details of degenerated cases, see [Ver10]. The Local Empty Property is depicted in figure 3a, it is due to circumcircles enclosing more than three points, whereas in figure 3b, for every triangle, the circumcircle encloses three points.

Delaunay Tetrahedralization is based on extending Delaunay Triangulation to three dimensions. Sequence of insertion of a point p in a Delaunay Triangulation. Because p falls into an edge, two adjacent triangles are affected; accordingly, four new triangles are created two for each affected triangle.

New edges are evaluated, the flipping process requires evaluation by using in Circle function, and the circumcircle is shown. Figure 4c shows the evaluation of a triangle; whereas figure 4d depicts the evaluation of other triangle.

The circumcircle of the flipping edges is depicted by colors. The final configuration of a Delaunay Triangulation is shown in figure 4e. Some steps have been ignored. The orientation can be calculated using equation 1, whereas the inCircle test can be calculated by using equation 2. Delaunay Tetrahedralization orientation test: Analogously, in three dimensions, the orientation test can be calculated using the determinant see equation 3 and the circumsphere test, usually called inSphere test, which is used to calculate a valid tetrahedron, it is shown in equation 4.

A Delaunay Triangulation was developed by using features extracted from the figure 5a in order to depict an easily identifiable triangulation. The features extracted were corners or interesting points from the image. In order to show the Delaunay triangulation; it gets salient features from an image to triangulate them.

In figure 5a the picture of Lena is depicted. Figure 5b shows the set of points extracted from the picture of Lena. Finally, using the set of points, a Delaunay Triangulation is constructed see figure 5c. The combination of the Tsukuba image and the Delaunay Triangulation from the image is shown in 6d; there are big triangles representing the human form white and the lamp orange because the colors are homogeneous and there are fewer features to extracting. Similarly, there are big triangles below the lamp because there are fewer features.

In contrast, the rest of the image has small triangles because more features can be A Review on Delaunay Triangulation with Application on Computer Vision 15 www. Moreover, the figure 6d shows the silhouette from the contrasting objects: Two interesting problems in computer vision are the Correspondence Estimation and the Motion Estimation. Correspondence estimation is based on establishing a pair of corresponding points from to slightly different images, which represent the same point in the real world.

The pair of images are taken from different points of view from correspondence estimation; in contrast, the definition of motion estimation is contrary, the images are taken from the same point of view and the difference between them is the time of the capture; usually, the images from motion estimation are called video or images sequence.

The questions are how can features extracted from images and Delaunay triangulation be used to track the objects inside the image? How can the Delaunay triangulation from stereo images be used to know either the depth and improve the disparity map construction or the objects motion by using motion vectors?

This paper is not trying to solve these questions, but is trying to identify the relationship between the Delaunay Triangulation and stereo images. Since the connection between similar objects is important for different problems in different areas, the capacity of Delaunay triangulation for maintains together the closest objects is significant. Even though the most known application of Delaunay Triangulation is the mesh, this geometry have been used in dozens of applications including medicine, terrain modeling, stereo correspondence, motion, video compression, amongst others.

Correspondence estimation involves the geometry from images; in the same way, Delaunay triangulation is widely known in geometry and widely used in computational geometry.

Both can be combined to explore the advantages from stereo images in order to impro.