### Topics

### features

### Publications

### Issue Archive

# Efficient Algorithm for Rectangular Spiral Search

- Wednesday, 29 October 2008

### The search pattern is automatically expanded as needed.

An algorithm generates grid coordinates for a computationally efficient spiral search pattern covering an uncertain rectangular area spanned by a coordinate grid. The algorithm does not require that the grid be fixed; the algorithm can search indefinitely, expanding the grid and spiral, as needed, until the target of the search is found. The algorithm also does not require memory of coordinates of previous points on the spiral to generate the current point on the spiral.

The search is started at a point (more precisely, in a grid
cell), denoted the center of the spiral, that has been chosen
previously as the point most likely to coincide with the target.
The search is to
be performed on a
grid of *n*×*m* cells,
where *m*>*n* and a ≡
*m* – *n* is denoted the
rectangular excess
of the search pattern
(see Figure 1).
The spiral search is
performed in steps
numbered simply 1,
2, 3..., and *t* represents
the number of
the current step.

The inputs to the algorithm are *t* and the rectangular
excess that is either specified in advance or calculated from
the rectangular grid used to span the initial search area. The
output of the algorithm is the pair of integer coordinates
(i,j) of the current point on the spiral with respect to the
center of the spiral. Figure 2 presents, as an example, the
first 15 steps of the spiral generated by this algorithm for a
search that starts at a point in a 3×5 rectangle.

*This work was done by Paul Brugarolas and William Breckenridge of
Caltech for NASA’s Jet Propulsion Laboratory.*

*The software used in this innovation is available for commercial licensing.
Please contact Karina Edmonds of the California Institute of
Technology at (626) 395-2322. Refer to NPO-42057.*

### White Papers

| ||||||