Created 2005-04-15 Modified 2007-01-01
Chelton Evans
Computational Geometry
You may not have noticed it but there is a war going on in the mathematics community - the continuous vs discrete mathematics, and the continuous is loosing, but is extracting a heavy price.
Of the 30 or so mathematicians at RMIT only a handful study discrete mathematics, and since its likely that they are classically trained they would bring with them the baggage from these fields and inject it into the new. I am pretty pessimistic with regard to other mathematicians and feel that future generations will have to clean up their drivel.
Most of them have no understanding of number theory and many years after Knuth's work they still have not read it - but there are many computer scientists in the same boat there too.
Anything that can be done with a continuous variable can be done with a discrete variable.
I rattle this mantra out to all the RMIT maths students I meet because I guarantee they would not learn it there - you just have to teach yourself. PS ITS TRUE. This means all the classical crap you have done could be done in another way.
Indeed you often have choices - the same problem could be done with an equality or by other algebraic methods.
The same war is going on in computational geometry. Even an expert like Joseph O'Rourke called for computational geometry to head back to its roots - that of the continuous variable and if I can find the quote in his book I will give it because its stupid.
I have brought attention to this because if you look at algorithms you need to see how they are thinking or to be more precise how they are not thinking.
If as do much of the algorithms they rely on geometric reasoning and reducing to special cases, and using the most minimal data structures points and edges - can lead to algorithms that do not generalize, are difficult to understand and plain wrong - for example there is no need to use angular algorithms to triangulate because there is so much better methods available, please do not do it.
Data structures is another major issue, for some reason the maths community forgot about the linked triangle and tetrahedron data structures. Instead using other methods like Delaunay Triangulation and extracting the graph. To give you an analogy lets consider the end result, construct an algorithm which achieve this an forget anything else that happened. While this way of thinking has benefits it is not healthy for the field to be looking at the end result in a similar way that businesses forget their business and focus on profit. The consequence of this attitude is a vast amount of literature that is not general or is ill informed.
What I hope to bring to the table is the interplay between dimensions and what common to the same algorithm or data structures in different dimensions.
For example writing an algorithm to connect two convex shapes together can be though of in both 2 and 3 dimensions. Comparing the two algorithms may result in seeing the common property across both dimensions that you would miss in one.
Further the data structure itself could be dimension dependent - I use triangles in 2D and tetrahedrons in 3D - the simplest data structures in those dimensions.
If you think that this is silly then think again - in approximating values like the square root of 2 the fastest approximators are done in the integer domain where a sequence of integers is generated where the ratio of two consecutive terms converges to the solution - continued fractions work this way - in sequences not calculus!
Here the result will be in the real numbers domain/dimension, but the simpler domain/dimension of integers was used.
In the same way you could consider the discrete domain its own dimension, and the continuous domain another dimension that contains the discrete one. However it will be advantageous and perhaps best to solve and do problems in the discrete domain instead of the continuous one.
Also thinking in a discrete way can solve other problems such as artifacts in meshes - where artifacts can be holes in the mesh surface. By using primitive shapes (triangle in 2D, tetrahedron in 3D) we can avoid artifacts in the marching triangles/tetrahedrons algorithms, a case where the algorithm is much cleaner and simpler, reduced ambiguities and a better result.
You may find what I am about to say not very nice but it needs to be said. Generality in mathematics lead to complete crap and lack of understanding in the theory of functional analysis. While they generalized the function they forgot to call it a derivative and instead called it a grad operator, often replacing it with a symbol. Now there is no algebra such as dF/dX were X is a vector, only a symbol of what is a derivative. I am incensed at this disassociation from algebra and lack of connection with algorithms - you can not do algebra on a symbol! It is not even partially wrong but totally wrong and I hope future mathematicians can todays mathematics for it. I have spoken with experts in the field of functional analysis and the concept of algebra on the grad operator has not even occurred in their entire lives ( Taylor series does not cut the mustard - it is just the beginning of a much larger picture and itself can be better expressed with algebra than is done in every text I have ever come across). They use other tools, mostly cumbersome for their work. <TODO>EVIDENCE This is not the generalization I want. I want to see the mathematics working and not be presented with mysterious black box stuff which works but says not how. I discovered to my surprise that often the people who use tools do not know why they work, even when they can prove the algorithm/tools work.