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.
 
 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
 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:
 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}
 \begin{equation}
        n = 2^{e} \times m
 \end{equation}


@@ -112,13 +116,31 @@ slow.
 
 
 \section{Quadtrees}
 
 
 \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]
 
 \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}
 \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}
 
 \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}
 }
 
   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
 
 % 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