Eyelids drooping, neurons not quite firing.

diff --git a/LitReviewDavid.pdf b/LitReviewDavid.pdf
index f3510f8..81a0594 100644 (file)
Binary files a/LitReviewDavid.pdf and b/LitReviewDavid.pdf differ

diff --git a/LitReviewDavid.tex b/LitReviewDavid.tex
index edd8b2b..b6e75cc 100644 (file)
--- a/LitReviewDavid.tex
+++ b/LitReviewDavid.tex
@@ -32,6 +32,10 @@ the content of the document to be explored in ways that perhaps the author had n
 However, these data-driven formats typically do not support fixed layouts, and the display differs from renderer to
 renderer.
 
+Ultimately, there are two fundamental stages by which all documents --- digital or otherwise --- are produced and displayed:
+\emph{layout} and \emph{display}. The \emph{layout} stage is where the positions and sizes of text and other graphics are
+determined, while the \emph{display} stage actually produces the final output, whether as ink on paper or pixels on a computer monitor.
+
 Existing document formats, due to being designed to model paper,
 have limited precision (8 decimal digits for PostScript\cite{plrm}, 5 decimal digits for PDF\cite{pdfref17}).
 This matches the limited resolution of printers and ink, but is limited when compared to what aught to be possible
@@ -86,7 +90,7 @@ which have the same cardinality as their \emph{unsigned} counterparts, but which
 represent integers between $-(2^{63})$ and $2^{63} - 1$}.
 
 Floating-point numbers\cite{goldberg1991whatevery} are the binary equivalent of scientific notation:
-each number consisting of an exponent ($e$) and a mantissa $(m)$ such that a number is given by
+each number consisting of an exponent ($e$) and a mantissa ($m$) such that a number is given by
 \begin{equation}
        n = 2^{e} \times m
 \end{equation}
@@ -112,13 +116,31 @@ slow.
 
 
 \section{Quadtrees}
-The quadtree is a data structure which keeps
-\cite{finkel1974quad}
+When viewing or processing a small part of a large document, it may be helpful to
+only processs --- or \emph{cull} --- parts of the document which are not on-screen.
 
 \begin{figure}[h]
-       \includegraphics[width=0.4\linewidth]{figures/quadtree_example}
+       \centering \includegraphics[width=0.4\linewidth]{figures/quadtree_example}
+       \caption{A simple quadtree.}
 \end{figure}
-
+The quadtree\cite{finkel1974quad}is a data structure --- one of a family of \emph{spatial}
+data structures --- which recursively breaks down space into smaller subregions
+which can be processed independently. Points (or other objects) are added to a single
+node, which if certain criteria are met --- typically the number of points in a node
+exceeding a maximum, though in our case likely the level of precision required exceeding
+that supported by the data type in use --- is split into four equal-sized subregions, and
+points attached to the region which contains them.
+
+In this project, we will be experimenting with a form of quadtree in which each
+node has its own independent coordinate system, allowing us to store some spatial
+information\footnote{One bit per-coordinate, per-level of the quadtree} within the
+quadtree structure, eliminating redundancy in the coordinates of nearby objects.
+
+Other spatial data structures exist, such as the KD-tree\cite{bentley1975multidimensional},
+which partitions the space on any axis-aligned line; or the BSP tree\cite{fuchs1980onvisible},
+which splits along an arbitrary line which need not be axis aligned. We believe, however,
+that the simpler conversion from binary coordinates to the quadtree's binary split make
+it a better avenue for initial research to explore.
 
 \bibliographystyle{unsrt}
 \bibliography{papers}

diff --git a/papers.bib b/papers.bib
index 4796a0b..8cd94c7 100644 (file)
--- a/papers.bib
+++ b/papers.bib
@@ -306,6 +306,45 @@ Goldberg:1991:CSK:103162.103163,
   publisher={Springer}
 }
 
+%BSP trees
+@inproceedings{fuchs1980onvisible,
+ author = {Fuchs, Henry and Kedem, Zvi M. and Naylor, Bruce F.},
+ title = {On Visible Surface Generation by a Priori Tree Structures},
+ booktitle = {Proceedings of the 7th Annual Conference on Computer Graphics and Interactive Techniques},
+ series = {SIGGRAPH '80},
+ year = {1980},
+ isbn = {0-89791-021-4},
+ location = {Seattle, Washington, USA},
+ pages = {124--133},
+ numpages = {10},
+ url = {http://doi.acm.org/10.1145/800250.807481},
+ doi = {10.1145/800250.807481},
+ acmid = {807481},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+} 
+
+% KD-tree paper
+@article{bentley1975multidimensional,
+ author = {Bentley, Jon Louis},
+ title = {Multidimensional Binary Search Trees Used for Associative Searching},
+ journal = {Commun. ACM},
+ issue_date = {Sept. 1975},
+ volume = {18},
+ number = {9},
+ month = sep,
+ year = {1975},
+ issn = {0001-0782},
+ pages = {509--517},
+ numpages = {9},
+ url = {http://doi.acm.org/10.1145/361002.361007},
+ doi = {10.1145/361002.361007},
+ acmid = {361007},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+ keywords = {associative retrieval, attribute, binary search trees, binary tree insertion, information retrieval system, intersection queries, key, nearest neighbor queries, partial match queries},
+} 
+
 
 % Basic overview of PDF and how it is awesome.
 % This doesn't seem like a major revelation for 2002

diff --git a/references/bentley1975multidimensional.pdf b/references/bentley1975multidimensional.pdf
new file mode 100644 (file)
index 0000000..953e49a
Binary files /dev/null and b/references/bentley1975multidimensional.pdf differ

diff --git a/references/fuchs1980onvisible.pdf b/references/fuchs1980onvisible.pdf
new file mode 100644 (file)
index 0000000..7ccb541
Binary files /dev/null and b/references/fuchs1980onvisible.pdf differ