| TR#: | CIS9626 |
| Class: | CIS |
| Title: | Dilation and Quadtrees - Theoretical and Practical Results |
| Authors: | Arnon Amir, Alon Efrat and Hanan Samet |
| Not 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1996/CIS/CIS9626), 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