Hi all,<br><br>First of all, I would like to apologise for not sending the report on Friday. This week was very busy for me, since I was moving away from England and I needed to sort various matters before I left, which kept me immensely occupied.<br>
<br>However, I had a fruitful conversation with Paul Kelly(my mentor). We were discussing algorithms I work with in detail. I have found out that the best way to fully understand something is to try to explain it to somebody else.<br>
<br>
I feel that I have acquired enough theoretical knowledge so that I can implement Guibas-Stolfi algorithm by the end of next week.<br><br>I know that many of you are really interested in the progress of SoC projects and some of you are even willing to give a hand to SoC students. For those who are interested, I attach a short summary of the conversation with my mentor below, which might be helpful to anybody who wants to be put on the right track about the progress of the project.<br>
<br>
Wolf Bergenheim recommended to me to have a look at <span style="font-style: italic;">Delaunay triangulations in TIN creation: an overview and a linear-time algorithm</span> (<a href="http://tinyurl.com/3s4s4h" target="_blank">http://tinyurl.com/3s4s4h</a>).
Unfortunately, my college is not subscribed to informaworld. If anybody
manages to get an electronic version of this paper, could you send it
to me. If not, then don't worry about that. I have plenty of other resources dealing with algorithms used for construction of DT&VD. I have uploaded most of it <a href="http://www.doc.ic.ac.uk/%7Emp107/delaunay-fun.zip" target="_blank">here</a> (7MB). You can have a look at those papers if you wish to. One of the disadvantage of some of those algorithms is that they are not so widely used and only a few implementations can be found online. The algorithms are also presented at a quite high theoretical level, which leaves a lot of implementation decisions on programmer, which is blessing and curse at the same time. They also require you to understand the theory used behind (mainly quad-edge data structure), which is a nice challenge.<br>
<br>I am primarily focusing on two particular algorithms.
Divide&Conquer algorithm by Guibas-Stolfi and plane-sweep algorithm
by Fortune. They both run in <i>N log N</i> worst case time. D&C algorithm
was initially presented using quad-edge data structure, which has many
nice properties. For instance, every single edge stores also its dual
edge, which means that a dual graph of the stored graph can be
easily obtained in linear time. In practice if you have constructed DT
you can get VD in linear time just by flipping every edge to its dual,
and vice versa for VD->DT(using the fact that DT and VD are dual to
each other). Another nice property is that topological representation
is entirely separated from geometrical one. Therefore altering one
keeps the other intact. Which I consider elegant from programmer's
point of view. However, those properties make this data structure quite
heavy in terms of memory usage, as Wolf have correctly pointed out. He
also suggested to use winged-edge instead, which is much less memory
demanding. Incidentally, one of the papers that is in the bundle I have
given you above, named <i>Improvements to Guibas-Stolfi and Fortune.pdf</i> have proposed
the same enhancement. This was driven mainly by observation that
traditional implementation of Guibas-Stolfi with quad-edge spends about
55% of the time of computation on various edge manipulating procedures.
In practice, winged-edge version of G-S uses less memory and is faster
than its quad-edge counterpart. Yet this costs us an option to easily
switch between graph and its dual. I plan to implement two versions of
G-S algorithm. At first I want to implement quad-edge version, since
this one was described in original paper and should be
*straightforward*. Then I will make another version with winged-edge. I
plan to give user an option as an optional parameter to choose if
he/she wants to be able to obtain also dual graph, if yes then
quad-edge will be used, otherwise winged-edge. Default should be
winged-edge for efficiency reasons.<br><br>In short, G-S works like this:<br><ol><li>Sort sites along x-axis with ties resolved by y-coordinate (this makes all future splittings constant time operations)<br></li><li>Recursively
divide the sites into left(L) and right(R) vertical slips. If a current
region contains 2 or 3 sites, construct DT directly, otherwise recurse
further. </li><li>Merge L-DT and R-DT (widely uses inCircle test)<br></li></ol>The
most complex of those steps is merge, which i am not going to explain,
since it has many substeps. It is nicely described (with pictures) in <i>Guibas-Stolfi divide-and-conquer.pdf</i> in the bundle above.<br>
<br>One major improvement to G-S is due by Dwyer, which improves expected time to <i>N log log N</i> for large number of distributions including uniform distribution in unit square. Dwyer advocates splitting a set of sites into cells = squares with
sides of length sqrt((log N)/N) (assuming the sites are in unit
square). Then you construct DT in each cell using traditional G-S
algorithm. In the next step you start merging DTs in cells in rows
using exactly the same method used for merging in G-S algorithm. You
merge(+) cells in this order: (0+1, 2+3, 4+5, ..., n+(n+1), ...)
storing results in cells (0, 2, 4, ...) then you merge (0+2, 4+6, ...,
(2k)+(2k+2), ...) storing results in (0, 4, 8, ...). You repeat this.
At the end, a triangulation of each row is stored in the cell at
position 0 in that row. Now you start merging rows in similar fashion.
However, slightly modified version of the merge proceduce has to be
used this time, since you are merging along bottom/top edges. Final DT
can be find in the cell (0,0).<br>
<br>Nonetheless, modified version of the above algorithm(name it DW2)
is implemented in practice, but the above is used to describe how the
algorithm works and for analysis of its efficiency.<br>In DW2 you split
the set of N sites into <i>sqrt(N/(log N))</i> slips by line parallel to
x-axis. Then you apply G-S to each slip. Remember that G-S splits sites
recursively into L and R halves by line parallel to y-axis - this
conspicuously resembles the above algorithm, but is somewhat easier to
implement. Next step is the same as in algorithm above, you merge rows.
Efficiency is rougly the same. Both run in expected time <i>N log log N</i>. If I have enough time I would like to implement DW2.<br><br>There are many other enhancements and speed ups mentioned in <i>Improvements to </i><i>Guibas-Stolfi and Fortune.pdf</i><i> </i>One
notable is an improved inCircle test which is largely used in the Merge
procedure. Usual version of computing determinant which after
elimination of common subexpressions takes 45 arithmetic operations is
improved to only 23 operations by using the test based on y-coordinate
of circumcircle centers. This can be further improved by caching, since
current top-most cross edge between L and R slips remains the same for
one iteration, some of the subexpressions remain constant and
precalculating them can decrease the number of operations of inCircle
to 15.<br>
<br>I have yet to study Fortune's plane-sweep algorithm in more detail.
There are many improvements applicable to plane-sweep algorithm also.<br>
<br>Regards,<br>Martin Pavlovsky<br><br>