\documentclass{article}
\usepackage{latexsym}
\usepackage{jgaa-article}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newenvironment{proof}{\par\addvspace\topsep\noindent
{\bf Proof:} \ignorespaces }{\qed}
\newcommand{\qed}{\hspace*{\fill}$\Box$\ifmmode\else\par\addvspace\topsep\fi}


\begin{document}

\Issue{2}{1}{1--23}{1997}

\HeadingAuthor{G. Liotta et al.}
\HeadingTitle{Robust Proximity Queries}

\Title{Robust Proximity Queries: an Illustration of Degree-driven
  Algorithm Design}

\Author{Giuseppe Liotta}
\Institution{
Dipartimento di Informatica e Sistemistica \\
Universit\'{a} di Roma ``La Sapienza'' \\
\Web{http://www.dis.uniroma1.it/} \\
\Email{liotta@dis.uniroma1.it}
}
\Author{Franco P. Preparata \And Roberto Tamassia}
\Institution{
Department of Computer Science \\
Brown University \\
\Web{http://www.cs.brown.edu/} \\
 \Email{franco@cs.brown.edu} \And \Email{rt@cs.brown.edu} \\
}

\begin{abstract}
  In the context of methodologies intended to confer robustness to
  geometric algorithms, we elaborate on the exact computation paradigm
  and formalize the notion of degree of a geometric algorithm, as a
  worst-case quantification of the precision (number of bits) to which
  arithmetic calculation have to be executed in order to guarantee
  topological correctness. We also propose a formalism for the
  expeditious evaluation of algorithmic degree. As an application of
  this paradigm and an illustration of our general approach where
  algorithm design is driven also by the degree, we consider the
  important classical problem of proximity queries in 2 and 3
  dimensions, and develop a new technique for the efficient and robust
  execution of such queries based on an implicit representation of
  Voronoi diagrams.  Our new technique offers both low degree and fast
  query time, and for 2D queries is optimal with respect to both cost
  measures of the paradigm, asymptotic number of operations and
  arithmetic degree.
\end{abstract}

\History{Communicated by G. Di Battista: submitted March 1997;
  revised June 1997.}

\Ack{Research supported in part by the U.S.\ Army Research Office
  under grant DAAH04--96--1--0013, and by the N.A.T.O.-C.N.R.\ 
  Advanced Fellowships Programme.}

\Body

\section{Introduction}

The increasing demand for efficient and reliable geometric software
libraries in key applications such as computer graphics, geographic
information systems, and computer-aided manufacturing is stimulating a
major renovation in the field of computational geometry.  The
inadequacy of the traditional simplified framework has become apparent,
and it is being realized that, in order to achieve an effective
technology transfer, new frameworks and models are needed to design and
analyze geometric algorithms that are efficient in a practical realm.

The real-RAM model with its implicit infinite-precision requirement,
has proved unrealistic and needs to be replaced with a realistic
finite-precision model where geometric computations can be carried out
either exactly or with a guaranteed error bound.  This has motivated a
great deal of research on the subject of robust computational
geometry.  For an early survey of the different approaches to robust
computational geometry the reader is referred to~\cite{h-pargc-89}.

To a first, rough, approximation, robustness approaches are of two
main types: perturbing and nonperturbing.  Perturbing approaches
transform the given problem into one that is intended not to suffer
from well-identified shortcomings; nonperturbing approaches are based
on the notion of ``exact'' (rather than ``approximate'') computations,
with the assumption that (bounded-length) input data are error free.
In this category falls the exact-geometric computation paradigm
independently advocated by Yap~\cite{y-tegc-97} and by the Saarbr\"ucken
school~\cite{bkmnsu-egcl-95}, and so does our approach.  Within this
paradigm, we introduce the notion of {\em degree} of an algorithm,
which describes, up to a small additive constant, the arithmetic
precision (i.e., number of bits) needed by the exact computation
paradigm.  Namely, if the coordinates of the input points of a
degree-$d$ geometric algorithm are $b$-bit integers, then, as we shall
substantiate below, the algorithm may be required on some instances to
perform arithmetic computations with bit precision $d(b+O(1))$.

 \dots

% ----------------------------------------------------------------------------

\section{Proximity Queries for Point Sites in the Plane} \label{se:ivd}

% ----------------------------------------------------------------------------

\dots

Let $S$ be a set of $n$ point sites in the plane, where each site is a
primitive point with $b$-bit integer coordinates.  The Voronoi diagram
$V(S)$ of $S$ is said to be {\em explicit} if the coordinates of the
vertices of $V(S)$ are computed and stored with exact arithmetic, i.e.,
as rational numbers (pairs of integers).

\begin{lemma} \label{le:conv-left-right}
  The $\mbox{leftright}(q,e)$ test primitive in an explicit Voronoi
  diagram of point sites in the plane has degree~$6$.
\end{lemma}

\begin{proof}
  Let $e\equiv(v_1,v_2)$ be a Voronoi edge such that $v_1 \equiv
  (x_1,y_1)$ is equidistant from three sites $a \equiv (x_a,y_a)$, $b
  \equiv (x_b,y_b)$, $c \equiv (x_c,y_c)$ and $v_2 \equiv (x_2,y_2)$
  is equidistant from three sites $b \equiv (x_b,y_b)$, $c \equiv
  (x_c,y_c)$, and $d \equiv (x_d,y_d)$.  In an explicit Voronoi
  diagram, test primitive $\mbox{leftright}(q,e)$ that determines
  whether query point $q \equiv (x_q,y_q)$ is to the left or to the
  right of edge $e \equiv(v_1,v_2)$ is equivalent to evaluating the
  sign of the following determinant:


        \[ \begin{array}{c}
        \Delta = \left| \begin{array} {ccc}
         x_q & y_q & 1 \\
         x_1 & y_1 & 1 \\
         x_2 & y_2 & 1
        \end{array} \right|  = 
        
         \left| \begin{array} {ccc}
         x_q & y_q & 1 \\
         \frac {X_1} {2W_1} & \frac {Y_1} {2W_1} & 1 \\
         \frac {X_2} {2W_2} & \frac {Y_2} {2W_2} & 1
        \end{array} \right|  
      \end{array} \]
where

\[ \begin{array} {cccc}
        X_1 = \left| \begin{array} {ccc}
        x_a^2 + y_a^2 & y_a & 1 \\
        x_b^2 + y_b^2 & y_b & 1 \\
        x_c^2 + y_c^2 & y_c & 1
        \end{array} \right|,&
        Y_1 = \left| \begin{array} {ccc}
        x_a & x_a^2 + y_a^2 & 1 \\
        x_b & x_b^2 + y_b^2 & 1 \\
        x_c & x_c^2 + y_c^2 & 1
        \end{array} \right|,&
        W_1 = \left| \begin{array} {ccc}
        x_a & y_a & 1 \\
        x_b & y_b & 1 \\
        x_c & y_c & 1
        \end{array} \right| 
        \end{array} 
 \]
%
and $X_2$, $Y_2$, and $W_2$ have similar expressions obtained replacing
in the above determinants $x_c$ with $x_d$ and $y_c$ with $y_d$.
Evaluating the sign of $\Delta$ is equivalent to evaluating the signs
of $W_1$, $W_2$ and of $\Delta'$.

We can rewrite $X_i$ and $Y_i$ as $\alpha^3$, and $W_i$ as $\alpha^2$
($i=1,2$).  Hence $\Delta'$ is a degree-$6$ polynomial, since it can
be rewritten as

        \[ 
        \begin{array}{llll}
        \alpha (\alpha^3 \alpha^2 -  \alpha^3 \alpha^2) - \alpha (
        \alpha^3 \alpha^2 -  \alpha^3 \alpha^2) + \alpha^3 \alpha^3 -
        \alpha^3 \alpha^3 & \longrightarrow^{(2,3,4)} & \alpha^6 +
        \alpha^6 \\
        &  \longrightarrow^{(3)}&
        \alpha^6.
        \end{array}\]
%
\end{proof}


        \dots

\section*{Acknowledgments}

The authors wish to thank the referees for several useful suggestions.

\clearpage 

\bibliographystyle{abbrv}
\bibliography{geom}

\end{document}

.