diff options
| author | Behdad Esfahbod <behdad@behdad.org> | 2007-04-08 22:56:30 -0400 |
|---|---|---|
| committer | Behdad Esfahbod <behdad@behdad.org> | 2007-04-08 22:56:30 -0400 |
| commit | 9da86e4a386505288c3a933f30583abf7706c950 (patch) | |
| tree | f4d240b1e7fd4d430826a5b8de00629babcece91 /BIBLIOGRAPHY | |
| parent | ad0e13805c036941a03e49215b1bb525b4666033 (diff) | |
Add references to the skiplist paper
Diffstat (limited to 'BIBLIOGRAPHY')
| -rw-r--r-- | BIBLIOGRAPHY | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/BIBLIOGRAPHY b/BIBLIOGRAPHY index 073e636d..dacd5321 100644 --- a/BIBLIOGRAPHY +++ b/BIBLIOGRAPHY @@ -60,6 +60,14 @@ algorithm for robustness against edges being "bent" due to restricting intersection coordinates to the grid available by finite-precision arithmetic. This is one algorithm we have not implemented yet. +We use a data-structure called Skiplists in the our implementation +of Bentley-Ottmann: + + W. Pugh, Skip Lists: a Probabilistic Alternative to Balanced Trees, + Communications of the ACM, vol. 33, no. 6, pp.668-676, 1990. + + http://citeseer.ist.psu.edu/pugh90skip.html + From the result of the intersection-finding pass, we are currently computing a tessellation of trapezoids, (the exact manner is undergoing some work right now with some important speedup), but we |