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.
 
 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}