Eyelids drooping, neurons not quite firing.

[ipdf/documents.git] / LitReviewDavid.tex

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}