Technical Report CIS9626

Title: Dilation and Quadtrees - Theoretical and Practical Results
Authors: Arnon Amir, Alon Efrat and Hanan Samet
PDFNot Available
Abstract: Let $S$ be a given shape in the plane, and let $B$ be a ball of a fixed radius. The dilation of $S$, denoted by D(S)$, is the shape resulting from taking the Minkowsky sum of S$S and $B$. $D(S)$ is the region consisting of all points in the plane whose distance from some point of $S$ is at most $r$. Computing the dilation of a shape is a common and important problem in the fields of robotics, image processing, computer graphics and in spatial databases where it corresponds to the spatial analog of a range query. Letting $T(S)$ be the quadtree representation of $S$, an algorithm (termed {\em Algorithm A}) is presented for calculating $D(T(S))$ in an optimal $O(n)$ time where $n$ is the number of blocks in $T(S)$. Algorithm A provides an analytic description of $D(T(S))$. However, in some applications, a result in the form of a quadtree is preferred. A second algorithm (termed {\em Algorithm C}) is presented that takes advantage of this output format requirement. It simplifies and applies some additional heuristics to Algorithm A resulting in a more practical algorithm, although one that is not asymptotically optimal which is the case for Algorithm A. This algorithm is currently implemented, and empirical results will be presented in the full paper.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion