Top 10 algorithms of the 20th century according to SIAM

Top 10 algorithms of the 20th century as ranked by SIAM editors . SIAM is the society of applied and industrial mathematics.Monte Carlo method ,Simplex method for linear programming and others included here

1957: John Backus leads a team at IBM in developing the Fortran optimizing compiler.
The creation of Fortran may rank as the single most important event in the history of computer programming: Finally, scientists(and others) could tell the computer what they wanted it to do, without having to descend into the netherworld of machine code.
Although modest by modern compiler standards—Fortran I consisted of a mere 23,500 assembly-language instructions—the early compiler was nonetheless capable of surprisingly sophisticated computations. As Backus himself recalls in a recent history of Fortran I, II, and III, published in 1998 in the IEEE Annals of the History of Computing, the compiler “produced code of such efficiency that its output would startle the programmers who studied it.”

Delaunay Triangulation

it’s official for Wikipedia : divide and conquer algorithms are the faster for Delaunay triangulation ,so to celebrate let’s talk about this specific algorithm for the triangulation of a set of points (2D or 3D) which is called grid and is used in many aspects of scientific computing.

DELAUNΑY TRIANGULATION

DT combines several quality measures : maxmin angle condition,minmax constrained circumcenter etc .DT of a point set is the planar dual of the Voronoi diagram.The Voronoi Diagram is a partition of the plane into polygonal cells, each of one assinged to an initial point., so that the cell for input point P consists of a region fo the plane closer to P than any other input point.Any point (nodal-point of the grid) lies outside the circumcentre and hence any vertex of the Voronoi diagram has degree 3 and the DT will be a triangulation.

There are many algorythms for DT.Some of them have to do with the Convex hull of the set points.The main idea goes like this : Lift each point of the input to a paraboloid in one dimension up (for 2D it will be 3D) ,by mapping the point ,to the point .The convex hull of the lifted points can be divided  into lower and upper parts: a face belongs tho the lower convex hull if it is supported by a plane that separates the point set from .It can be shown that the DT of the input points is the projection of the lower convex hull onto the xy-plane:

Many algorythms of run-time are developed for DT.One nice one and pretty understanding is devide_and_conquer .For the generall overview of the most famous algorythms for DT and their run-time comparison is triangulation_algorythms_sigkrisi.

SOURCE CODE

you can try to compute the delauney triangulation from source code for your input data points from here (Fortran 90,C,C++)

Automatic triangulation of planar domain # cavendish algorithm

Let’s assume we want to construct a grid over an arbitrary planar domain filling it with triangles .We can use Cavendish’s semi automatic triangulation algorithm  . This algorithm  which will be described generates meshes with triangular elements for the decomposition of a region giving a special advantage to the user to specify the density of the elements , giving that way a mesh , appropriate to the physical and boundary conditions . The algorithm uses a modified algorithm  from the Suhara-Fukuda algorithm and goes like this :

DEFINING THE AREA (interior , boundary nodes and density of elements)

For instance , let’s assume we want to generate a triangular mesh over a circular domain with circle in it ( hole) .We call the domain R. The user is first required to make an arcwise (multiply) .

The domain R with counter-clockwise ordering of boundary nodes

connected polygonal approximation R to the planar structure to be triangulated.The boundary must be composed of a disjoint union of simple, closed, piecewise linear arcs.

In order to provide the facility for triangulations of varying node density, the user is required to cover the region R with a disjoint set of simply connected polygonal zones   , In particular, for each zone user is required to specify (in counter-clockwise order) the x-y co-ordinates which serve to define the boundary
For each zone  there must be an accompanying density factor  > 0.

Zonal decomposition of R

In order to get triangles with very avute angles , we demand all the nodes to lie in the interior area that is defined by the boundary elements .

NODES GENERATING

Starting from node 1 and moving counter clockwise , the algorithm circumscribes the smallest rectangle in the zone Z which belongs .To make things clearer we superimpose a rectangular grid with unit equal to the density .Our purpose is to to randomly generate one interior node in each sub-square of the grid .

Generation of interior node points

Thus applying this to all the other sub-domains Zi we get the interior nodes . As many as five consecutive attempts are made to generate a retainable random point in any one sub-square. If no point is successfully generated after five consecutive attempts, then no node is designated in that sub-square and the next sub-square is considered. This process is repeated until all sub-squares have been tested .The flow chart of the method is the following :

But we are not done . there must be an algorithm that will precises the interconnections of the nodes by checking the neighborhood of each edge such that the choice of the 3rd node , will give as acute interior angels . But this will be discussed latter …