Journal of Graph Algorithms and Applications

   http://www.cs.brown.edu/publications/jgaa/

vol. 2, no. 1, pp. 1–23 (1997)

Robust Proximity Queries: an Illustration of Degree-driven Algorithm Design

Giuseppe Liotta

Dipartimento di Informatica e Sistemistica Universitá di Roma “La Sapienza”

               http://www.dis.uniroma1.it/
                 liotta@dis.uniroma1.it

Franco P. Preparata Roberto Tamassia

Department of Computer Science Brown University

                http://www.cs.brown.edu/
          franco@cs.brown.edu   rt@cs.brown.edu

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.

Communicated by G. Di Battista: submitted March 1997; revised June 1997.

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.

1 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 [2].

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 [3] and by the Saarbrücken school [1], and so does our approach. Within this paradigm, we introduce the notion of 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)).

…

2 Proximity Queries for Point Sites in the Plane

…

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

Lemma 1 The leftright(q, e) test primitive in an explicit Voronoi diagram of point sites in the plane has degree 6.

Proof: Let e ≡ (v_{1}, v_{2}) be a Voronoi edge such that v_{1} ≡ (x_{1}, y_{1}) is equidistant from three sites a ≡ (x_{a}, y_{a}), b ≡ (x_{b}, y_{b}), c ≡ (x_{c}, y_{c}) and v_{2} ≡ (x_{2}, y_{2}) is equidistant from three sites b ≡ (x_{b}, y_{b}), c ≡ (x_{c}, y_{c}), and d ≡ (x_{d}, y_{d}). In an explicit Voronoi diagram, test primitive leftright(q, e) that determines whether query point q ≡ (x_{q}, y_{q}) is to the left or to the right of edge e ≡ (v_{1}, v_{2}) is equivalent to evaluating the sign of the following determinant:

Δ = | \begin{matrix}x_{q} & y_{q} & 1 \\ x_{1} & y_{1} & 1 \\ x_{2} & y_{2} & 1 \end{matrix} | = | \begin{matrix}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{matrix} |

where

X_{1} = | \begin{matrix}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{matrix} | , Y_{1} = | \begin{matrix}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{matrix} | , W_{1} = | \begin{matrix}x_{a} & y_{a} & 1 \\ x_{b} & y_{b} & 1 \\ x_{c} & y_{c} & 1 \end{matrix} |

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 Δ is equivalent to evaluating the signs of W_{1}, W_{2} and of Δ′.

We can rewrite X_{i} and Y_{i} as α^{3}, and W_{i} as α^{2} (i = 1, 2). Hence Δ′ is a degree-6 polynomial, since it can be rewritten as

\begin{aligned}α(α^{3}α^{2} − α^{3}α^{2}) − α(α^{3}α^{2} − α^{3}α^{2}) + α^{3}α^{3} − α^{3}α^{3} & ⟶^{(2,3,4)} & α^{6} + α^{6} \\ & ⟶^{(3)} & α^{6}. \end{aligned}

□

…

Acknowledgments

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

References

[1] C. Burnikel, J. Könnemann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig. Exact geometric computation in LEDA. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C18–C19, 1995.

[2] C. M. Hoffmann. The problems of accuracy and robustness in geometric computation. IEEE Computer, 22(3):31–41, Mar. 1989.

[3] C. Yap. Towards exact geometric computation. Comput. Geom. Theory Appl., 7:3–23, 1997.